Cho dãy số \(A\) có \(n\) phần tử \(a_1,a_2,...,a_n\) và \(q\) truy vấn \(l\) \(r\) \(k\). Với mỗi truy vấn \(l\) \(r\) \(k\). Hãy kiểm tra xem tích của các phần tử \(a_l,a_{l+1},...,a_r\) có chia hết cho \(k\) hay không.

Dữ liệu vào

Nhập dữ liệu từ tệp CHIAHET.INP có cấu trúc như sau:
Dòng đầu tiên chứa số nguyên dương \(n\) - là số lượng phần tử của dãy \(A\).
Dòng thứ hai chứa \(n\) số nguyên dương \(a_1,a_2,...,a_n\) lần lượt là các phần tử của dãy \(a\).
Dòng thứ ba chứa số nguyên dương \(q\) - Số lượng truy vấn
\(q\) dòng tiếp theo, mỗi dòng chứa mỗi truy vấn \(l\) \(r\) \(k\).

Dữ liệu ra

Ghi dữ liệu ra tệp CHIAHET.OUT theo cấu trúc như sau:
Gồm \(q\) dòng, mỗi dòng in ra YES nếu tích các phần tử của đoạn con ấy chia hết cho \(k\), ngược lại in ra NO.

Chấm điểm

Tất cả các test đều thỏa mãn điều kiện \(1 \leq n \leq 10^5, 1 \leq q \leq 10^5, 1 \leq a_i \leq 10^9, 2 \leq k \leq 10\)

• Các test từ \(1\) đến \(30\) có ràng buộc riêng \(1 \leq n \leq 10^3, 1 \leq q \leq 10^3\).
• Các test từ \(31\) đến \(60\) tiếp theo có ràng buộc riêng \(1 \leq n \leq 10^3, 1 \leq q \leq 10^5\)
• Các test từ \(61\) đến \(80\) tiếp theo có ràng buộc riêng \(k=2\) với mọi truy vấn
• \(20\) test còn lại đảm bảo ràng buộc gốc.

4 
9 2 2 7
2
1 3 3
2 4 3

YES
NO

Cho hai dãy số \(A\) và \(B\), mỗi dãy gồm \(n\) phần tử.Tạo một dãy mới \(C\) bằng cách lấy tổng của mọi cặp phần tử giữa hai dãy, tức là: \(C=\{A_i+B_j∣1≤i,j≤n\}\). Nói cách khác, với mỗi phần tử của \(A\), ta cộng với từng phần tử của \(B\). Vì có \(n\) phần tử trong mỗi dãy nên dãy \(C\) sẽ có \(n^2\) giá trị.
Ví dụ \(A=\{1,2,3\}; B=\{4,5,6\}\), ta sẽ có dãy \(C=\{5,6,6,7,7,7,8,8,9\}\).

Yêu cầu

Hãy sắp xếp dãy \(C\) theo thứ tự tăng dần và in ra giá trị của phần tử thứ \(k\). Biết rằng phần tử đầu tiên của dãy \(C\) được đánh chỉ số là \(1\).

Dữ liệu vào

Dữ liệu nhập từ tệp NEWARRAY.INP có cấu trúc như sau:

• Dòng đầu tiên chứa 2 số nguyên dương \(n\), \(k\) \((1\leq n,k\leq 10^5, 1\leq k\leq n^2 )\).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, ..., a_n\) \((1\leq a_i\leq 10^9)\).
• Dòng thứ ba chứa \(n\) số nguyên dương \(b_1, b_2, ..., b_n\) \((1\leq b_i\leq 10^9)\).

Dữ liệu ra

Dữ liệu ghi ra tệp NEWARRAY.OUT theo cấu trúc như sau:

• Dòng \(1\): In ra tổng lớn thứ \(k\) tìm được.

Chấm điểm

• Subtask \(1(60\%\) số test\()\): \(n \leq 10^3\).
• Subtask \(2(40\%\) số test\()\): Không có ràng buộc gì thêm.

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

9

Cho dãy số \(a\) có \(n\) phần tử lần lượt là \(k,k+1,k+2,...,n+k-1\). Hãy tìm chỉ số \(i\) sao cho \(x=|a_1+a_2+a_3+...+a_i-a_{i+1}-a_{i+2}-...-a_n|\) là bé nhất có thể. Ký hiệu \(|x|\) biểu diễn giá trị tuyệt đối của \(x\).

Input

Dữ liệu nhập từ tệp ARRAY.INP có cấu trúc như sau:

• Dòng đầu tiên chứa số nguyên dương \(t (1 \leq n \leq 10^4)\)
• \(t\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(n,k (1 \leq n,k \leq 10^9)\) lần lượt là số lượng phần tử của dãy số và điểm bắt đầu của dãy số.

Output

Dữ liệu xuất ra tệp ARRAY.OUT theo cấu trúc như sau:
- Với mỗi test case, hãy in ra kết quả |x| tìm được.

Subtask

• Subtask \(1(30\%\) số điểm\()\) có \(t \leq 10,1 \leq n,k \leq 10^6\).
• Subtask \(2(70\%\) số điểm\()\) không có ràng buộc gì thêm.

4
2 2
7 2
5 3
1000000000 1000000000

1
5
1
347369930

Cho dãy \(a\) có \(n\) phần tử \(a_1,a_2,a_3,...,a_n\). Hãy đếm số lượng cặp số \((i,j)\) sao cho \(1 \leq i < j \leq n\) và \(3a_i+2a_j=S\).

Input

Dữ liệu nhập từ tệp CAPSO.INP có cấu trúc như sau:

• Dòng \(1\): Chứa hai số tự nhiên \(n\) và \(S\)
• Dòng \(2\): Chứa \(n\) số tự nhiên \(a_1,a_2,...,a_n\).

Output

Dữ liệu ghi ra tệp CAPSO.OUT theo cấu trúc như sau:
- Dòng \(1\): Số lượng cặp số tìm được.

Subtasks

• \(70\%\) số điểm có \(n \leq 10^3\)
• \(30\%\) số điểm còn lại có \(n \leq 10^6\)

Tất cả các test đều đảm bảo \(0 \leq a_i \leq 10^6, 0 \leq S \leq 10^{18}\)

5 10
1 2 1 1 2

1