Kamioni

Παρατηρούμε την κίνηση \(Ν\) φορτηγών στο δρόμο. Ο δρόμος μπορεί να αναπαρασταθεί ως αριθμητική γραμμή. Τα σημεία στη γραμμή που δηλώνουν πόλεις είναι ακέραιοι. Οι πόλεις συμβολίζονται με τον αριθμό του αντίστοιχου σημείου στη γραμμή.

Όλα τα φορτηγά κινούνται με την ίδια ταχύτητα και κανένα φορτηγό δεν στέκεται ακίνητο ανά πάσα στιγμή. Κάθε φορτηγό χρειάζεται 1 λεπτό για να διανύσει την απόσταση μεταξύ δύο γειτονικών πόλεων.

Σας δίνεται η διαδρομή κάθε φορτηγού. Όλα τα φορτηγά ξεκινούν τη διαδρομή τους την ίδια αρχική στιγμή.

Η διαδρομή δίνεται ως μια σειρά από ~k~ πόλεις: ~A_1 ,\; A_2 ,\; ..., \;A_k~ . Το φορτηγό ξεκινά από την πόλη ~A_1~ και οδηγεί στην πόλη ~A_2~, μετά στρίβει και οδηγεί στην πόλη ~A_3~ και ούτω καθεξής. Δεδομένου του γεγονότος ότι το φορτηγό στρίβει, θα κρατήσει:

~A_1 < A_2 > A_3 < A_4 >\;\ldots\;~ ή ~\;A_1 > A_2 < A_3 > A_4 <\;\ldots~

Ο χρόνος που χρειάζεται για να στρίψει το φορτηγό είναι αμελητέος.

Μια πιθανή διαδρομή είναι ~2,\;5,\;1,\;7~. Το φορτηγό βρίσκεται στην πόλη νούμερο 2 αρχικά, 3 λεπτά μετά την αναχώρηση φτάνει στην πόλη νούμερο 5. Στρίβει και συνεχίζει προς την πόλη νούμερο 1 στην οποία φτάνει 7 λεπτά μετά την αναχώρηση. Στρίβει ξανά και οδηγεί προς την πόλη νούμερο 7 στην οποία φτάνει τη στιγμή 13.

Αφού το φορτηγό ολοκληρώσει τη διαδρομή του, εμφανίζονται εξωγήινοι και το απομακρύνουν στον διαστημικό πύραυλο τους.

Για μερικά ζευγάρια φορτηγών, θέλουμε να μάθουμε πόσες φορές συναντήθηκαν στο δρόμο. Με άλλα λόγια, πόσες φορές φάνηκαν να βρίσκονται στην ίδια θέση (η θέση που συνάντησαν δεν χρειάζεται να είναι ακέραιος, δηλαδή θα μπορούσαν να έχουν συναντήσει στη θέση ~2.5~).

Γράψτε ένα πρόγραμμα που, για έναν δεδομένο αριθμό ~N~ φορτηγών και τις διαδρομές τους και για ~M~ ζεύγη φορτηγών, θα καθορίζει τον αριθμό των συναντήσεων για κάθε ζεύγος.

Σημείωση: κάθε ζευγάρι φορτηγών για το οποίο θέλουμε να γνωρίζουμε τον αριθμό των συναντήσεων, θα ισχύει:

• δεν θα βρίσκονται στο ίδιο μέρος τη στιγμή που ένας από αυτούς (ή και οι δύο) θα παρασυρθούν από εξωγήινους
• δεν θα είναι στο ίδιο μέρος την αρχική στιγμή ή τη στιγμή που ένας από αυτούς (ή και οι δύο) γυρίζουν

Η επάνω δήλωση δεν ισχύει για όλα τα ζεύγη φορτηγών, αλλά μόνο για τα ζευγάρια για τα οποία θέλουμε να γνωρίζουμε τον αριθμό των συναντήσεων.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τους ακέραιους αριθμούς ~N~ και ~M\;(1 \leq N \leq 10^5,\;1 \leq M \leq 10^5)~, τον αριθμό των φορτηγών και τον αριθμό των ζευγών φορτηγών για τα οποία θέλουμε να γνωρίζουμε τον αριθμό των συναντήσεων.

Η i-οστή από τις ακόλουθες ~N~ γραμμές περιέχει την περιγραφή της διαδρομής του i-οστού φορτηγού.

Ο πρώτος ακέραιος στη γραμμή, ~K_i\;(2 \leq K_i \leq 3 \times 10^5)~ αντιπροσωπεύει τον αριθμό των πόλεων στη διαδρομή του φορτηγού. Μετά από αυτό ακολουθούν οι ακέραιοι αριθμοί ~K_i,\;A_j\;(1 \leq A_j \leq 10^9 )~, οι τακτικοί αριθμοί των πόλεων στη διαδρομή του φορτηγού που δίνονται με τη σειρά που το φορτηγό τις επισκέπτεται.

Το άθροισμα των διαδρομών όλων των φορτηγών δεν θα υπερβαίνει τα ~3 \times 10^5~ . Κάθε μία από τις ακόλουθες ~M~ γραμμές περιέχει δύο ακέραιους αριθμούς ~(a_i,\;b_i)~, τους τακτικούς αριθμούς των φορτηγών για τους οποίους θέλουμε να γνωρίζουμε τον αριθμό των συναντήσεων.

Έξοδος

Τυπώστε ~N~ γραμμές. Η ~i~-οστή γραμμή πρέπει να περιέχει τον αριθμό των συναντήσεων του ~i~-οστού ζεύγους φορτηγών από την είσοδο.

Βαθμολογία

Στις περιπτώσεις δοκιμής αξίας ~50~% των συνολικών πόντων, θα έχει ~N \leq 10^2,\;K_i \leq 10^3,\;M \leq 10^3~.

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

input

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

output

1
0
2

input

2 1
4 1 6 3 6
7 3 4 2 6 4 5 6 1
1 2

output

3

input

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

output

2
1
2
2