Quốc tế thiếu nhi 2020

Flow God có \(n\) em gái. Sau khi cùng các em làm việc nhà trong ngày sinh nhật của mình, Flow God và các em gái được bố mẹ thưởng kẹo. Mức thưởng được xét dựa trên năng lực: Làm ít ăn ít, làm nhiều ăn nhiều. Em gái thứ \(i\) được thưởng \(a_i\) viên kẹo, còn Flow God được thưởng \(x\) viên kẹo.

Flow God rất rộng lượng nhưng các em gái thì không. Nói cách khác, Flow God có thể đem kẹo của mình cho các em nhưng các em gái thì chỉ nhận kẹo mà không bao giờ chia sẻ cho ai khác. Là một người con trung thành với lý tưởng Xã Hội Chủ Nghĩa, Flow God muốn số kẹo của mọi người phải bằng nhau. Để thực hiện điều đó, anh có thể lấy vài viên kẹo của mình cho vài em gái. Flow God tự hỏi liệu mình có thể làm mọi người bình đẳng được không?

Input

• Dòng đầu tiên chứa một số nguyên dương \(t\), số trường hợp mà Flow God cần giúp đỡ (Flow God có nhiều nhóm em gái khác nhau ...)

Với mỗi trường hợp:

• Dòng đầu tiên chứa \(2\) số nguyên \(n, x\)
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, ..., a_n\)

Output

• In ra \(t\) dòng, mỗi dòng chứa đáp số cho trường hợp tương ứng. In ra "YES" nếu Flow God có thể đạt được ước nguyện làm cho thế giới bình đẳng, "NO" nếu ngược lại.

Constraints

• \(t \leq 10^5\)
• \(1 \leq n \leq 10^5, 0 \leq x \leq 10^9\)
• \(0 \leq a_i \leq 10^9\)
• Tổng các số \(n\) trong một input không vượt quá \(10^5\)

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(a_1=a_2=...=a_n=0\).
• Subtask \(2\) (\(30\%\) số điểm): \(a_1=a_2=...=a_n\).
• Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.

Example

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

YES
NO
YES

Nhân ngày quốc tế thiếu nhi, ami đã tặng em gái của Flow God xấu-trai-hơn-ami một chiếc máy thần kì. Trên chiếc máy là 2 nút màu tím và hồng, cùng 2 số \(H\) và \(I\). Nếu ấn nút màu tím, số \(H\) sẽ tăng 1 đơn vị, nếu ấn nút màu hồng, số \(I\) sẽ tăng 1 đơn vị. Flow God ghen tuông vì ami đã tặng cho em gái cưng của mình một món quà cool ngầu như thế, bèn tìm ra cách để ami phải mất mặt.

Flow God xấu-trai-hơn-ami muốn ami ấn các nút tím và hồng tổng cộng không quá F lần. Sau khi thực hiện các thao tác, giả sử 2 số mà ami nhận được là \(N\) và \(R\), Flow God muốn \(gcd(N,R)\) là lớn nhất có thể. Nhắc lại, \(gcd(a,b)\) là một số \(c\) lớn nhất mà cả \(a\) và \(b\) đều chia hết cho \(c\) (quy ước \(gcd(0, n)=gcd(n, 0)=n\) với mọi số nguyên dương \(n\)). Tuy nhiên, ami quá thần thánh, đã tìm ra kết quả siêu nhanh. Flow God tức tối, giận cuom1999 chém ma. "ma" ở đây chính là các bạn tham gia contest.

Các bạn cần trả lời \(q\) câu hỏi của Flow God, mỗi câu hỏi có dạng \(H\) \(I\) \(F\). Cần in ra \(gcd(N,R)\) lớn nhất, \(N\) và \(R\) là các số nhận được, sau khi ấn hai nút tím và hồng không quá \(F\) lần.

Input

• Dòng đầu tiên chứa một số nguyên dương \(q\) là số câu hỏi của Flow God xấu-trai-hơn-ami.
• Tiếp theo là \(q\) dòng, mỗi dòng chứa một bộ số nguyên không âm \(H\) \(I\) \(F\) là một câu hỏi.

Output

• In ra \(q\) dòng, mỗi dòng là một số nguyên là \(gcd(N,R)\) lớn nhất có thể đạt được.

Dữ liệu đảm bảo luôn có kết quả.

Constraints

• \(H, I \leq 10^5\)
• \(q \leq 10^2\)
• \(F \leq 10^{13}\)

Scoring

• Subtask \(1\) (\(5\%\) số điểm): \(H = 0, I \leq 10^5, F \leq 10^{13}, q \leq 10^2\).
• Subtask \(2\) (\(20\%\) số điểm): \(H, I \leq 10^5, q \leq 10^2, F \leq 10^{5}\).
• Subtask \(3\) (\(10\%\) số điểm): \(H, I \leq 10^5, q \leq 10^2, F = 0\)
• Subtask \(4\) (\(65\%\) số điểm): \(H, I \leq 10^5, q \leq 10^2, F \leq 10^{13}\)

Example

3
0 1 1
1 1 2
2 4 1

2
2
2

Cho một bảng gồm \(m\) hàng và \(n\) cột. Ô ở hàng \(i\), cột \(j\) chứa số nguyên dương \(a_{i,j}\).

Bạn cần trả lời \(q\) truy vấn. Mỗi truy vấn cho hai ô \((x_1,y_1)\) và \((x_2,y_2)\), trong đó \(x_1 \le x_2\) và \(y_1 \le y_2\). Từ một ô, bạn chỉ có thể đi sang ô kề bên phải hoặc ô kề bên dưới. Khi đi vào ô \((i,j)\), bạn phải trả chi phí \(a_{i,j}\).

Với mỗi truy vấn, hãy tìm tổng chi phí nhỏ nhất để đi từ \((x_1,y_1)\) đến \((x_2,y_2)\). Chi phí của ô xuất phát không được tính; chi phí của mọi ô đi vào sau đó, bao gồm ô đích, đều được tính.

Input

• Dòng đầu tiên chứa hai số nguyên \(m,n\).
• \(m\) dòng tiếp theo, mỗi dòng chứa \(n\) số nguyên; số thứ \(j\) trên dòng thứ \(i\) là \(a_{i,j}\).
• Dòng tiếp theo chứa số nguyên \(q\).
• Mỗi trong \(q\) dòng tiếp theo chứa bốn số nguyên \(x_1,y_1,x_2,y_2\), mô tả một truy vấn.

Output

Với mỗi truy vấn, in ra trên một dòng tổng chi phí nhỏ nhất tìm được.

Constraints

• \(1 \le m,n \le 100\).
• \(1 \le a_{i,j} \le 10^6\).
• \(1 \le q \le 10^6\).
• \(1 \le x_1 \le x_2 \le m\).
• \(1 \le y_1 \le y_2 \le n\).

Scoring

• Subtask 1 (\(30\%\) số điểm): \(a_{i,j}=1\) với mọi ô.
• Subtask 2 (\(30\%\) số điểm): \(q \le 10^4\).
• Subtask 3 (\(40\%\) số điểm): Không có ràng buộc gì thêm.

Example

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

9
7
3

Cho hai số nguyên dương \(n, k\). Đếm xem có bao nhiêu hoán vị \(p_{1}, p_{2}, \ldots, p_{n}\) của \(1, 2, \ldots, n\) thỏa mãn \(p_{i} > p_{i / k}\) với mọi \(1 \leq i \leq n\).

Trong đó, \(a / b\) là số nguyên lớn nhất không vượt quá \(\dfrac{a}{b}\) và quy ước \(p_{0} = 0\).

Input

• Gồm hai số nguyên dương \(n, k\) \((1 \leq n, k \leq 10^{6})\).

Output

• In ra số lượng hoán vị thỏa mãn điều kiện sau khi \(\mod (10^{9} + 7)\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \leq 10\).
• Subtask \(2\) (\(10\%\) số điểm): \(k > n\).
• Subtask \(3\) (\(10\%\) số điểm): \(k = n\).
• Subtask \(4\) (\(20\%\) số điểm): \(k > \dfrac{n}{2}\).
• Subtask \(5\) (\(20\%\) số điểm): \(n, k \leq 10^{3}\).
• Subtask \(6\) (\(20\%\) số điểm): \(n, k \leq 10^{6}\).

Example

3 2 

2

8 3 

2520