Εξάπλωση φάρσας

Ο Pak Dengklek μόλις δημιούργησε έναν ιστότοπο κοινωνικής δικτύωσης. Υπάρχουν \(Ν\) χρήστες που χρησιμοποιούν τον ιστότοπο, με αριθμό από ~0~ έως ~N - 1~. Υπάρχουν ~S~ ώρες σε μία ημέρα. Όλοι οι χρήστες έχουν ένα σταθερό πρόγραμμα χρήσης από μέρα σε μέρα. Για κάθε ~i~ τέτοιο ώστε ~0 \le i \le N - 1~, ο χρήστης ~i~ είναι συνδεδεμένος ~T[i]~ φορές κάθε μέρα:

• από την έναρξη της ~A[i][0]~^ης ώρας έως το τέλος της ~B[i][0]~^ης ώρας,
• από την αρχή της ~A[i][1]~^ης ώρας έως το τέλος της ~B[i][1]~^ης ώρας,
• ~\ldots~
• και από την έναρξη της ~A[i][T[i] - 1]~^ης ώρας έως το τέλος της ~B[i][T[i] - 1]~^ης ώρας.

Ανά πάσα στιγμή, όλοι οι χρήστες στον ιστότοπο επιθυμούν να μοιράζονται νέα με όλους τους άλλους χρήστες που βρίσκονται στον ιστότοπο. Δυστυχώς, ένας από τους ~N~ χρήστες έχει μία φάρσα (hoax) στην αρχή της πρώτης ημέρας και θα τη διαδώσει. Ως εκ τούτου, όλοι οι χρήστες που συναντούν το χρήστη με τη φάρσα θα έχει επίσης τη φάρσα στο τέλος της πρώτης ημέρας. Δύο χρήστες θεωρούμε ότι συναντώνται εάν υπάρχει τουλάχιστον μία ώρα όπου και οι δύο χρήστες είναι συνδεδεμένοι.

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

Υπάρχουν ~Q~ σενάρια, το καθένα από τα οποία μπορεί να αναπαρασταθεί ως ακέραιος αριθμός ~P~. Για κάθε σενάριο, ο χρήστης που έχει τη φάρσα στην αρχή της πρώτης ημέρας είναι ο χρήστης ~P~. Ένα διαφορετικό σενάριο μπορεί να προκαλέσει διαφορετικό εξάπλωμα φάρσας. Επομένως, για κάθε σενάριο, ο Pak Dengklek αναρωτιέται για τον αριθμό των χρηστών με τη φάρσα στο τέλος της ~N~^ης ημέρας, όπου ~N~ είναι ο αριθμός των χρηστών.

Λεπτομέρειες Υλοποίησης

Θα πρέπει να εφαρμόσετε τις ακόλουθες διαδικασίες:

void init(int N, int S, int[] T, int[][] A, int[][] B)

• ~N~ : ο αριθμός των στοιχείων στους πίνακες ~T~ , ~A~ και ~B~.
• ~S~ : ο αριθμός των ωρών σε μία ημέρα.
• ~T~ : ένας πίνακας μήκους ~N~ που περιγράφει πόσες φορές κάθε χρήστης θα είναι συνδεδεμένος καθημερινά.
• ~A~, ~B~ : πίνακες μήκους ~N~. Οι ~A[i]~ και ~B[i]~ είναι πίνακες μήκους ~T[i]~ που περιγράφουν πότε ο χρήστης ~i~ θα να είναι συνδεδεμένος κάθε μέρα.
• Αυτή η διαδικασία καλείται ακριβώς μία φορά, πριν από οποιαδήποτε κλήση της count_users.

int count_users(int P)

• ~P~ : ο δείκτης του χρήστη που έχει τη φάρσα στην αρχή της πρώτης ημέρας.
• Αυτή η διαδικασία θα πρέπει να επιστρέφει τον αριθμό των χρηστών με τη φάρσα στο τέλος της ~N~^ης ημέρας, όπου ~N~ είναι ο αριθμός των χρηστών.
• Αυτή η διαδικασία καλείται ακριβώς ~Q~ φορές.

Παράδειγμα

Εξετάστε την ακόλουθη σειρά κλήσεων:

init(5, 10, [2, 1, 1, 1, 1],
[[2, 7], [1], [1], [9], [5]], [[4, 9], [3], [1], [10], [6]]

count_users (0)

Αυτό σημαίνει ότι ο χρήστης 0 έχει τη φάρσα στην αρχή της πρώτης ημέρας. Ο χρήστης 0 συναντά τον χρήστη 1 (στη δεύτερη ώρα έως την τρίτη ώρα) και τον χρήστη 3 (την ένατη ώρα). Επομένως, στο τέλος της πρώτης ημέρας, οι δύο χρήστες θα έχουν τη φάρσα. Ο χρήστης 1 επίσης συναντά τον χρήστη 2 (την πρώτη ώρα). Ως εκ τούτου, στο τέλος της δεύτερης μέρας, ο χρήστης 2 θα έχει επίσης τη φάρσα. Δεν θα υπάρξει διάδοση της φάρσας την τρίτη, τέταρτη, και πέμπτη ημέρα, επομένως 4 χρήστες θα έχουν τη φάρσα στο τέλος της πέμπτης ημέρας. Συνεπώς, η διαδικασία πρέπει να επιστρέψει 4.

count_users (4)

Αυτό σημαίνει ότι ο χρήστης 4 έχει τη φάρσα στην αρχή της πρώτης ημέρας. Ο χρήστης 4 δεν συναντά άλλους χρήστες, επομένως άλλοι χρήστες δε θα έχουν τη φάρσα. Ως εκ τούτου, η διαδικασία θα πρέπει να επιστρέψει 1.

Περιορισμοί

• ~1 \le N \le 200\, 000~
• ~1 \le S \le 10^9~
• ~1 \le Q \le 100\, 000~
• ~1 \le T[i] \le S~ (για κάθε ~i~ έτσι ώστε ~0 \le i \le N - 1~)
• Το άθροισμα όλων των στοιχείων του \(Τ\) δεν υπερβαίνει τις ~200\, 000~.
• ~1 \le A[i][j] \le B[i][j] \le S~ (για κάθε ~i~ και ~j~ έτσι ώστε ~0 \le i \le N - 1~ και ~0 \le j \le T[i] - 1~ )
• ~B[i][j - 1] < A[i][j]~ (για κάθε ~i~ και ~j~ έτσι ώστε ~0 \le i \le N - 1~ και ~1 \le j \le T[i] - 1~)
• ~0 \le P \le N - 1~
• Οι τιμές του ~P~ μεταξύ όλων των σεναρίων είναι ξεχωριστές κατά ζεύγη.

Υποπροβλήματα

1. (15 βαθμοί) ~N~, ~S~, ~Q \le 50~ και το άθροισμα όλων των στοιχείων του ~T~ δεν υπερβαίνει το 50.
2. (17 μονάδες) ~N~, ~Q \le 50~ και το άθροισμα όλων των στοιχείων του ~T~ δεν υπερβαίνει το 50.
3. (21 βαθμοί) ~N~, ~Q \le 300~ και το άθροισμα όλων των στοιχείων του ~T~ δεν υπερβαίνει το 300.
4. (26 μονάδες) ~N~, ~Q \le 2000~ και το άθροισμα όλων των στοιχείων του ~T~ δεν υπερβαίνει το 2000.
5. (21 βαθμοί) Χωρίς πρόσθετους περιορισμούς.

Υπόδειγμα βαθμολογητή

Ο βαθμολογητής δείγματος διαβάζει την είσοδο στην ακόλουθη μορφή:

• γραμμή ~1~: ~N~ ~S~ ~Q~
• γραμμή ~2 + i~ ~(0 \le i \le N - 1)~: ~T[i] A[i][0] B[i][0] \ldots A[i][T[i] - 1] B[i][T[i] - 1]~
• γραμμή ~2 + N + k~ ~(0 \le k \le Q - 1)~: ~P~ για το σενάριο ~k~

Το δείγμα βαθμολογητή εκτυπώνει τις απαντήσεις σας στην ακόλουθη μορφή:

• γραμμή ~1 + k~ ~(0 \le k \le Q - 1)~: η επιστρεφόμενη τιμή της count_users για το σενάριο ~k~