Beyond Counting

Ο Andy Jiang μελετά δομές δεδομένων. Μια μέρα, ο φίλος του Austin Zhu τού έδωσε ένα πρόβλημα σχετικά με δέντρα.

Ο Austin έδωσε ένα δέντρο με ~N~ κορυφές, αριθμημένες από ~1~ έως ~N~. Κάθε κορυφή ~i~ έχει μια τιμή ~A_i~.

Για κάθε ερώτημα, ο Austin ζήτησε από τον Andy να εξετάσει ένα μονοπάτι ανάμεσα σε δύο κορυφές ~s_i~ και ~t_i~ και να υπολογίσει πόσες φορές εμφανίζεται μια δεδομένη τιμή ~x_i~ σε αυτό το μονοπάτι.

Ο Andy έριξε μια ματιά στο πρόβλημα και σκέφτηκε ότι ήταν υπερβολικά εύκολο για εκείνον.

Αντί να μετρά απλώς τις εμφανίσεις, ο Andy αποφάσισε να προκαλέσει τον εαυτό του ακόμη περισσότερο. Για κάθε ερώτημα, θέλει να μάθει πώς συγκρίνεται η συχνότητα εμφάνισης του ~x_i~ με τις συχνότητες εμφάνισης άλλων τιμών στο ίδιο μονοπάτι.

Πιο συγκεκριμένα, για κάθε ερώτημα ~(s_i, t_i, x_i)~:

• Θεωρήστε το απλό μονοπάτι από την κορυφή ~s_i~ έως την κορυφή ~t_i~.

• Έστω ~cnt(y)~ ο αριθμός των εμφανίσεων της τιμής ~y~ σε αυτό το μονοπάτι.

Ο Andy ορίζει την κατάταξη του ~x_i~ ως

~1 + |\{y \mid cnt(y) > cnt(x_i)\}|~.

Δηλαδή, ένα συν τον αριθμό των διαφορετικών τιμών που εμφανίζονται συχνότερα από το ~x_i~ στο μονοπάτι. Σημειώστε ότι είναι πιθανό η τιμή ~x_i~ να μην εμφανίζεται καθόλου στο μονοπάτι, δηλαδή ~cnt(x_i) = 0~. Σε αυτή την περίπτωση, πρέπει να επιστρέψετε ένα συν τον αριθμό των διαφορετικών τιμών που εμφανίζονται στο μονοπάτι.

Σε ορισμένες περιπτώσεις ελέγχου, τα ερωτήματα δίνονται σε κωδικοποιημένη μορφή, όπως περιγράφεται παρακάτω.

Βοηθήστε τον Andy να υπολογίσει την κατάταξη του ~x_i~ για κάθε ερώτημα.

Είσοδος

Η πρώτη γραμμή θα περιέχει τρεις θετικούς ακέραιους αριθμούς ~N~, ~Q~ και ~T~ (~1 \le N, Q \le 10^5~, ~T \in \{0, 1\}~).

Η δεύτερη γραμμή θα περιέχει ~N~ ακέραιους αριθμούς ~A_1, A_2, \ldots, A_N~ (~1 \le A_i \le 10^9~).

Οι επόμενες ~N - 1~ γραμμές θα περιέχουν από δύο ακέραιους αριθμούς ~u_i~, ~v_i~ (~1 \le u_i, v_i \le N~), που αναπαριστούν την ~i~-οστή ακμή.

Καθεμία από τις επόμενες ~Q~ γραμμές θα περιέχει τρεις ακέραιους αριθμούς ~\hat{s_i}~, ~\hat{t_i}~, ~\hat{x_i}~ (~1 \le \hat{s_i}, \hat{t_i} \le N~, ~1 \le \hat{x_i} \le 10^9~), οι οποίοι περιγράφουν το ~i~-οστό ερώτημα.

Έστω ~last_0 = 0~. Για κάθε ερώτημα ~i = 1, 2, \ldots, Q~, οι πραγματικές παράμετροι ορίζονται ως εξής:

~s_i = ((\hat{s_i} + last_{i-1} \times T - 1) \bmod N) + 1~,

~t_i = ((\hat{t_i} + last_{i-1} \times T - 1) \bmod N) + 1~,

~x_i = ((\hat{x_i} + last_{i-1} \times T - 1) \bmod 10^9) + 1~.

Αφού υπολογίσετε την απάντηση στο ~i~-οστό ερώτημα, θέστε ~last_i =~ απάντηση αυτού του ερωτήματος.

Είναι επίσης χρήσιμο να γνωρίζετε ότι το ~mod~ αντιστοιχεί στον τελεστή % στις περισσότερες γλώσσες προγραμματισμού και δηλώνει το υπόλοιπο της διαίρεσης. Για παράδειγμα, ~5 \bmod 3 = 2~ και ~17 \bmod 4 = 1~.

Ο παρακάτω πίνακας δείχνει πώς κατανέμονται οι ~25~ διαθέσιμοι βαθμοί:

Βαθμοί	Όρια των ~N~, ~Q~, ~T~	Επιπλέον περιορισμοί
~1~	~1 \le N, Q \le 10^3~, ~T = 1~	Κανένας επιπλέον περιορισμός.
~1~	~1 \le N, Q \le 10^5~, ~T = 0~	Όλα τα ~s_i~ είναι ίσα.
~4~	~1 \le N, Q \le 10^5~, ~T = 1~	Όλα τα ~s_i~ είναι ίσα.
~4~	~1 \le N, Q \le 10^5~, ~T = 0~	~u_i = i~ και ~v_i = i + 1~.
~5~	~1 \le N, Q \le 10^5~, ~T = 1~	~u_i = i~ και ~v_i = i + 1~.
~3~	~1 \le N, Q \le 10^5~, ~T = 0~	Κανένας επιπλέον περιορισμός.
~7~	~1 \le N, Q \le 10^5~, ~T = 1~	Κανένας επιπλέον περιορισμός.

Έξοδος

Για κάθε ερώτημα, να εκτυπώσετε την απάντηση σε ξεχωριστή γραμμή.

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

input

5 5 0
1 2 3 4 4
4 3
2 5
1 3
3 2
4 5 3
4 5 4
4 5 5
1 5 1
1 5 4

output

2
1
4
1
1

input

5 5 1
1 2 3 4 4
4 3
2 5
1 3
3 2
4 5 3
2 3 2
3 4 4
2 1 999999997
5 4 3

output

2
1
4
1
1