Relativnost

Ο νεαρός Luka είναι έμπορος έργων τέχνης. Έχει N πελάτες και πουλάει καλλιτεχνικούς πίνακες σε κάθε πελάτη. Κάθε πελάτης μπορεί να αγοράσει είτε έγχρωμους πίνακες είτε ασπρόμαυρους πίνακες, αλλά όχι και τους δύο. Ο πελάτης που δηλώνεται με το ~i~ θέλει να αγοράσει το πολύ ~a_i~ έγχρωμους πίνακες και το πολύ ~b_i~ ασπρόμαυρους πίνακες.
Ο πελάτης θα αγοράζει πάντα τουλάχιστον έναν πίνακα. Ο Luka έχει σχεδόν απεριόριστο αριθμό έργων ζωγραφικής, επομένως ο αριθμός των πινάκων που απαιτούνται από τους πελάτες δεν αποτελεί ποτέ πρόβλημα. Του Luka δεν του αρέσει να πουλά ασπρόμαυρους πίνακες και ξέρει ότι αν λιγότεροι από ~C~ άνθρωποι πάρουν έγχρωμους πίνακες, θα τον κάνει να λυπηθεί.

Οι πελάτες του αλλάζουν συνεχώς τα αιτήματά τους ή, με άλλα λόγια, τον αριθμό των πινάκων που θέλουν να αγοράσουν. Εξαιτίας αυτού, ο Luka συχνά προβληματίζεται από την ερώτηση: "Πόσες διαφορετικές αγορές υπάρχουν, έτσι ώστε τουλάχιστον ~C~ πελάτες να έχουν τουλάχιστον έναν έγχρωμο πίνακα;" Βοηθήστε τον Luka και σώστε τον από τις ανησυχίες του.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει δύο ακέραιους ~N,\;C\;(1 \leq N \leq 100\,000,\;1 \leq C \leq 20)~.
Η δεύτερη γραμμή εισόδου περιέχει ~N~ ακέραιους αριθμούς ~a_i\;(1 \leq a_i \leq 1\,000\,000 000)~.
Η τρίτη γραμμή εισόδου περιέχει ~N~ ακέραιους ~b_i\;(1 \leq b_i \leq 1 000\,000\,000)~.
Η τέταρτη γραμμή εισόδου περιέχει τον αριθμό των αλλαγών απαίτησης ~Q\;(1 \leq Q \leq 100\,000)~.

Κάθε μία από τις ακόλουθες γραμμές ~Q~ περιέχει τρεις ακέραιους αριθμούς, την ετικέτα του ατόμου που αλλάζει τις απαιτήσεις ~P\;(1 \leq P \leq N)~, τον μέγιστο αριθμό έγχρωμων πινάκων που θέλουν να αγοράσουν ~a_P\;(1 \leq a_P \leq 1\,000\,000\,000)~ και τον μέγιστο αριθμό ασπρόμαυρων πινάκων που θέλουν να αγοράσουν ~b_P\;(1 \leq b_P \leq 1\,000\,000\,000)~.

Έξοδος

Η έξοδος πρέπει να αποτελείται από γραμμές Q όπου κάθε γραμμή περιέχει τον αριθμό των διαφορετικών αγορών modulo 10 007.

Βαθμολογία

Σε περιπτώσεις δοκιμής αξίας 30% των συνολικών πόντων, θα ισχύει ότι το ~N~ και το ~Q~ είναι μικρότερα από 1000.

Παραδείγματα

input

2 2
1 1
1 1
1
1 1 1

output

1

Επεξήγηση του 1ου παραδείγματος:

Αφού ο πρώτος πελάτης αλλάξει το αίτημά του από ~(1,\;1)~ σε ~(1,\;1)~ - τίποτα δεν αλλάζει πραγματικά, ο αριθμός των τρόπων πώλησης έργων ζωγραφικής είναι 1. Ο ένας και μοναδικός τρόπος για να πουλήσετε πίνακες είναι να πουλήσετε στον πρώτο πελάτη έναν έγχρωμο ζωγραφική και στον δεύτερο πελάτη θα πρέπει να πουληθεί επίσης ένας έγχρωμος πίνακας. Κάθε πελάτης πρέπει να πάρει τουλάχιστον έναν έγχρωμο πίνακα γιατί ~C = 2~, που σημαίνει ότι θα πρέπει να υπάρχουν τουλάχιστον 2 πελάτες με έγχρωμους πίνακες.

input

2 2
1 2
2 3
2
1 2 2
2 2 2

output

4
4

input

4 2
1 2 3 4
1 2 3 4
1
4 1 1

output

66