Andy Jiang đang nghiên cứu về cấu trúc dữ liệu. Một ngày nọ, người bạn Austin Zhu của cậu đã đưa ra một bài toán trên cây.
Austin cho một cái cây có $N$ đỉnh, được đánh số từ $1$ đến $N$. Mỗi đỉnh $i$ có một giá trị $A_i$.
Với mỗi truy vấn, Austin yêu cầu Andy xét đường đi giữa hai đỉnh $s_i$ và $t_i$, và tính xem một giá trị cho trước $x_i$ xuất hiện bao nhiêu lần trên đường đi đó.
Andy nhìn qua bài toán và nghĩ rằng nó quá dễ đối với mình.
Thay vì chỉ đếm số lần xuất hiện, Andy quyết định thử thách bản thân hơn. Với mỗi truy vấn, cậu muốn biết tần suất của $x_i$ so với các giá trị khác trên cùng đường đi đó.
Một cách hình thức, với mỗi truy vấn $(s_i, t_i, x_i)$: Xét đường đi đơn từ $s_i$ đến $t_i$. Gọi $cnt(y)$ là số lần xuất hiện của giá trị $y$ trên đường đi này.
Andy định nghĩa thứ hạng (rank) của $x_i$ là: $$1 + |\{y \mid cnt(y) > cnt(x_i)\}|$$
Nghĩa là, một cộng với số lượng các giá trị phân biệt xuất hiện thường xuyên hơn $x_i$ trên đường đi. Lưu ý rằng có khả năng giá trị $x_i$ không xuất hiện trên đường đi, tức là $cnt(x_i) = 0$. Trong trường hợp này, bạn nên trả về một cộng với số lượng các giá trị phân biệt trên đường đi.
Trong một số bộ dữ liệu, các truy vấn được đưa ra dưới dạng mã hóa như mô tả bên dưới.
Hãy giúp Andy tính thứ hạng của $x_i$ cho mỗi truy vấn.
Dữ liệu vào
Dòng đầu tiên chứa ba số nguyên dương $N, Q$ và $T$ ($1 \le N, Q \le 10^5, T \in \{0, 1\}$). Dòng thứ hai chứa $N$ số nguyên $A_1, A_2, \dots, A_N$ ($1 \le A_i \le 10^9$). $N - 1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u_i, v_i$ ($1 \le u_i, v_i \le N$), biểu diễn cạnh thứ $i$. Mỗi dòng trong $Q$ dòng tiếp theo chứa ba số nguyên $\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$), mô tả truy vấn thứ $i$.
Đặt $last_0 = 0$. Với mỗi truy vấn $i = 1, 2, \dots, Q$, các tham số thực tế được xác định như sau: $s_i = ((\hat{s}_i + last_{i-1} \times T - 1) \pmod N) + 1$ $t_i = ((\hat{t}_i + last_{i-1} \times T - 1) \pmod N) + 1$ $x_i = ((\hat{x}_i + last_{i-1} \times T - 1) \pmod{10^9}) + 1$
Sau khi tính toán câu trả lời cho truy vấn thứ $i$, đặt $last_i = \text{câu trả lời cho truy vấn thứ } i$.
Cũng cần lưu ý rằng "mod" tương ứng với toán tử % trong hầu hết các ngôn ngữ lập trình, biểu thị phần dư sau phép chia. Ví dụ, $5 \pmod 3 = 2$ và $17 \pmod 4 = 1$.
Nhiệm vụ con
Bảng sau đây cho thấy cách phân bổ 25 điểm:
| Điểm | Giới hạn $N, Q$ | Giới hạn $T$ | Ràng buộc bổ sung |
|---|---|---|---|
| 1 điểm | $1 \le N, Q \le 10^3$ | $T = 1$ | Không có |
| 1 điểm | $1 \le N, Q \le 10^5$ | $T = 0$ | Tất cả $s_i$ đều bằng nhau |
| 4 điểm | $1 \le N, Q \le 10^5$ | $T = 1$ | Không có |
| 4 điểm | $1 \le N, Q \le 10^5$ | $T = 0$ | $u_i = i$ và $v_i = i + 1$ |
| 5 điểm | $1 \le N, Q \le 10^5$ | $T = 1$ | $u_i = i$ và $v_i = i + 1$ |
| 3 điểm | $1 \le N, Q \le 10^5$ | $T = 0$ | Không có |
| 7 điểm | $1 \le N, Q \le 10^5$ | $T = 1$ | Không có |
Dữ liệu ra
Với mỗi truy vấn, in ra câu trả lời cho truy vấn trên một dòng mới.
Ví dụ 1
Dữ liệu vào 1
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
Dữ liệu ra 1
2 1 4 1 1
Ví dụ 2
Dữ liệu vào 2
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
Dữ liệu ra 2
2 1 4 1 1