Bài tập

Trong một thiên hà xa xôi, một nền văn minh cổ đại đã phát triển một hệ thống số học phức tạp để đo lường năng lượng của các vì sao. Năng lượng của một chòm sao, được biểu diễn bằng một số nguyên không âm \(a\), khi được kích hoạt bởi một hằng số vũ trụ \(b\), sẽ tạo ra một giá trị năng lượng mới. Giá trị này được tính toán bằng phép toán luỹ thừa, nhưng để tránh sự quá tải năng lượng, kết quả phải được lấy theo một modulo đặc biệt, là \(10^9 + 7\).

Tuy nhiên, có một trường hợp đặc biệt mà các nhà thiên văn học cổ đại đã ghi chép lại: khi một chòm sao có năng lượng ban đầu là 0 được kích hoạt bởi hằng số 0, nó sẽ tạo ra một năng lượng kích hoạt cơ bản bằng 1.

Bạn là một nhà toán học vũ trụ, được giao nhiệm vụ giải mã những công thức cổ đại này. Bạn cần xây dựng một chương trình để tính toán giá trị năng lượng cuối cùng cho một loạt các chòm sao và hằng số vũ trụ được đưa ra.

Yêu cầu: Cho các cặp số nguyên không âm \((a, b)\), hãy tính giá trị \(a^b \pmod{10^9 + 7}\). Lưu ý rằng theo quy tắc đặc biệt, \(0^0 = 1\).

Input

• Dòng đầu tiên chứa một số nguyên \(n\) (\(1 \le n \le 2 \cdot 10^5\)), là số lượng câu hỏi.
• \(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a, b\) (\(0 \le a, b \le 10^9\)).

Output

• In ra \(n\) dòng, mỗi dòng chứa một số nguyên là kết quả của phép tính \(a^b \pmod{10^9 + 7}\) tương ứng với mỗi cặp \((a, b)\) trong dữ liệu vào.

Example

3
3 4
2 8
123 123

81
256
921450052

Scoring

• Subtask \(1\) (\(50\%\) số điểm) : \(n, a, b \leq 1000\).
• Subtask \(2\) (\(50\%\) số điểm) : không có ràng buộc gì thêm.

Cho mảng \(A\) gồm \(n\) số nguyên và \(q\) truy vấn. Mỗi truy vấn là một số nguyên \(k\).

Với mỗi truy vấn, hãy tìm độ dài lớn nhất của một đoạn con liên tiếp mà tất cả các phần tử trong đó đều không vượt quá \(k\).

\InputFile

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) --- số phần tử của mảng và số truy vấn.
• Dòng thứ hai chứa \(n\) số nguyên \(A_1, A_2, \dots, A_n\).
• \(q\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(k\) --- một truy vấn.

Giới hạn:

• \(1 \le n \le 10^5\)
• \(0 \le |A_i|, |k| \le 10^9\)

\OutputFile
Với mỗi truy vấn, in ra một dòng chứa kết quả --- độ dài đoạn con dài nhất thỏa điều kiện.

Example

6 4
-2 5 6 10 -5 0
-10
5
-4
11

0
2
1
6

BT đang chơi một trò chơi gọi là "Nền văn minh". Bạn hãy giúp BT chơi trò chơi đó.

Trò chơi có \(n\) thành phố và \(m\) con đường vô hướng. Các thành phố được đánh số từ \(1\) đến \(n\). Giữa hai thành phố bất kỳ hoặc có một đường đi duy nhất hoặc không có đường đi nào cả. Một đường đi là một dãy các thành phố khác nhau \(v_1, v_2, ..., v_k\) sao cho giữa hai thành phố liên tiếp \(v_i\) và \(v_{i+1}\) \((1 \leq i < k)\) có một con đường nối chúng. Chiều dài của đường đi này bằng \(k-1\).

Chúng ta nói rằng hai thành phố cùng một vùng khi và chỉ khi có đúng một đường đi kết nối hai thành phố này.

BT muốn trả lời hai loại truy vấn sau:

• "1 x": Tìm chiều dài đường đi dài nhất trong vùng chứa thành phố \(x\).
• "2 x y": Kiểm tra xem thành phố \(x\) và thành phố \(y\) có cùng một vùng hay không. Nếu không, BT cần phải hợp nhất hai vùng như sau: chọn một thành phố trong vùng thứ nhất và một thành phố trong vùng thứ hai, nối chúng bằng một con đường sao cho chiều dài của đường đi dài nhất trong vùng hợp nhất là nhỏ nhất có thể. Nếu có nhiều cách làm như vậy, bạn được phép chọn một cách bất kỳ.

Bạn hãy giúp BT trả lời các câu hỏi loại 1 và thực hiện các yêu cầu loại 2.

Input

• Dòng đầu tiên chứa ba số nguyên \(n, m, q\) \((1 \leq n \leq 3 \times 10^5; 0 \leq m \leq n; 1 \leq q \leq 3 \times 10^5)\) --- số thành phố, số con đường ban đầu và số truy vấn.
• Mỗi trong số \(m\) dòng tiếp theo chứa hai số nguyên \(a_i\) và \(b_i\) \((1 \leq a_i, b_i \leq n, a_i \neq b_i)\) --- mô tả một con đường nối hai thành phố \(a_i\) và \(b_i\). Có thể có nhiều nhất một con đường nối hai thành phố.

• Mỗi trong số \(q\) dòng tiếp theo chứa một truy vấn thuộc một trong hai dạng:

• "1 x": Xác định chiều dài của đường đi dài nhất trong vùng chứa thành phố \(x\) \((1 \leq x \leq n)\). Dữ liệu đảm bảo luôn có ít nhất một truy vấn dạng này.

• "2 x y": Hợp nhất vùng của thành phố \(x\) và vùng của thành phố \(y\) \((1 \leq x, y \leq n, x \neq y)\).

Output

Với mỗi câu hỏi dạng thứ nhất, in ra kết quả trên một dòng.

Example

10 3 9
1 2
1 3
2 4
1 2
2 1 1
2 7 9
2 3 2
2 2 7
2 2 5
1 6
2 7 4
1 7

3
0
4

Cho mảng \(a\) gồm \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\) và số nguyên dương \(M\). Một đoạn con liên tiếp của mảng \(a\) là một dãy gồm các phần tử liên tiếp có dạng: \(a_i, a_{i+1}, \dots, a_j\) \((1 \le i \le j \le n)\), độ dài là \(j-i+1\).

Trung vị của một đoạn con liên tiếp \(b\) có độ dài \(k\) được định nghĩa như sau:

• Sắp xếp các phần tử của \(b\) theo thứ tự không giảm.

• Khi đó:

• Nếu \(k\) lẻ: Trung vị là phần tử ở vị trí \((k+1)/2\).

• Nếu \(k\) chẵn: Trung vị là phần tử ở vị trí \(k/2\).

Yêu cầu: Hãy đếm số lượng đoạn con liên tiếp của mảng \(a\) có trung vị bằng \(M\).

Input

Vào từ tệp văn bản BAI4.INP có cấu trúc:

• Dòng thứ nhất chứa hai số nguyên dương \(n,M\) \((1 \le M < n \le 10^6)\).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\) \((a_i \le 10^6; 1 \le i \le n)\).

Output

Ghi ra tệp văn bản BAI4.OUT một số nguyên duy nhất là kết quả của bài toán.

Example

5 2
2 1 3 4 5

3

Scoring

• Có \(40\%\) số test ứng với \(40\%\) số điểm của bài thỏa mãn: \(n \le 10^2\).
• Có \(30\%\) số test khác ứng với \(30\%\) số điểm của bài thỏa mãn: \(10^2 < n \le 5 \times 10^3\).
• \(30\%\) số test còn lại ứng với \(30\%\) số điểm của bài không có ràng buộc gì thêm.