Số đặc biệt là số nguyên dương có đúng ~3~ ước số.

Ví dụ: ~4~ là số đặc biệt vì có ~3~ ước là ~1, 2~ và ~4~.

Yêu cầu

Cho hai số nguyên dương ~a~ và ~b~, hãy đếm số lượng số đặc biệt trong đoạn ~[a, b]~.

Dữ liệu đầu vào

Gồm hai số nguyên dương ~a,\ b~ ~(1 \le a \le b \le 10^9)~.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là kết quả tìm được.

Ràng buộc dữ liệu

• 70% điểm có ~1 \le a \le b \le 10^3~.

Ví dụ

Ví dụ 1

INPUT

5 30

OUTPUT

2

Giải thích: Đoạn ~[5, 30]~ có hai số ~9~ và ~25~ là số đặc biệt.

Cho dãy số nguyên gồm ~n~ phần tử, đoạn con của dãy đã cho là đoạn gồm các phần tử liên tiếp của dãy đó. Độ hoàn hảo của đoạn con là trung bình cộng các phần tử của đoạn con đó.

Yêu cầu

Hãy tìm đoạn con có độ hoàn hảo lớn nhất và tổng các phần tử lớn hơn hoặc bằng ~k~ cho trước.

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng đầu tiên chứa hai số nguyên ~n,\ k~ ~(1 \le n \le 10^5;\ |k| \le 10^{10})~;
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~ ~(|a_i| \le 10^9,\ 1 \le i \le n)~.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là phần nguyên của độ hoàn hảo lớn nhất tìm được, nếu không tìm được kết quả ghi NO.

Ràng buộc dữ liệu

• 30% số điểm có ~1 \le n \le 10^2~;
• 40% số điểm có ~10^2 < n \le 10^3~.

Ví dụ

Ví dụ 1

INPUT

5 6
1 5 4 2 3

OUTPUT

4

Giải thích: Đoạn con ~[5, 4]~ có tổng các phần tử ~\ge 6~ và độ hoàn hảo lớn nhất bằng ~4{,}5~. Kết quả ghi ra phần nguyên của ~4{,}5~ là ~4~.

Ví dụ 2

INPUT

3 6
1 -5 2

OUTPUT

NO

Giải thích: Không có đoạn con nào có tổng lớn hơn hoặc bằng ~6~.

Công ty HP có hai tổ hoàn thiện sản phẩm, tổ ~1~ có ~m~ công nhân, tổ ~2~ có ~n~ công nhân. Giám đốc yêu cầu ~2~ tổ phải hoàn thiện ~m + n~ sản phẩm sao cho:

• Mỗi công nhân phải hoàn thiện ~1~ sản phẩm;
• Sản phẩm ~i~ ~(1 \le i \le m + n)~ nếu giao cho tổ ~1~ hoàn thiện mất ~a_i~ giây, nếu giao cho tổ ~2~ hoàn thiện thì mất ~b_i~ giây.
• Một số sản phẩm chỉ có thể giao cho tổ ~1~ hoàn thiện, ngược lại một số sản phẩm chỉ có thể giao cho tổ ~2~ hoàn thiện.

Yêu cầu

Bạn hãy giúp giám đốc công ty giao việc cho các công nhân ~2~ tổ sao cho tổng thời gian hoàn thiện ~m + n~ sản phẩm của các công nhân là nhỏ nhất.

Dữ liệu đầu vào

Gồm ~m + n + 1~ dòng:

• Dòng đầu tiên ghi hai số nguyên dương ~m,\ n~ ~(1 \le m, n \le 10^5)~;
• ~m + n~ dòng tiếp theo, dòng thứ ~i~ ~(1 \le i \le m + n)~ là ba số ~a_i, b_i, c_i~ ~(1 \le a_i, b_i \le 10^6)~:
  • ~c_i = 0~ sản phẩm ~i~ có thể hoàn thiện bởi công nhân của cả ~2~ tổ;
  • ~c_i = 1~ sản phẩm ~i~ chỉ được hoàn thiện bởi công nhân tổ ~1~;
  • ~c_i = 2~ sản phẩm ~i~ chỉ được hoàn thiện bởi công nhân tổ ~2~.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là tổng thời gian ít nhất để hoàn thiện ~m + n~ sản phẩm. Dữ liệu vào đảm bảo luôn hoàn thiện ~m + n~ sản phẩm.

Ràng buộc dữ liệu

• 15% số điểm có ~m = 1, n = 1~;
• 15% số điểm có ~c_i \ne 0~ ~(\forall\ i: 1 \le i \le m + n)~;
• 40% số điểm có ~1 < m, n \le 10~.

Ví dụ

Ví dụ 1

INPUT

1 1
9 8 0
7 8 0

OUTPUT

15

Giải thích:

• Tổ ~1~ hoàn thiện sản phẩm ~2~ hết ~7~ giây;
• Tổ ~2~ hoàn thiện sản phẩm ~1~ hết ~8~ giây;

Tổng thời gian hoàn thiện ~2~ sản phẩm là ~7 + 8 = 15~ giây.

Ví dụ 2

INPUT

2 3
5 2 0
8 5 1
1 6 2
1 5 0
2 9 0

OUTPUT

23

Giải thích:

• Tổ ~1~ hoàn thiện sản phẩm ~2~ và ~5~ hết ~8 + 2 = 10~ giây;
• Tổ ~2~ hoàn thiện sản phẩm ~1, 3~ và ~4~ hết ~2 + 6 + 5 = 13~ giây;

Tổng thời gian hoàn thiện ~5~ sản phẩm là ~10 + 13 = 23~ giây.

Cho một ma trận kích thước ~n \times n~, ô giao dòng ~i~ và cột ~j~ được gọi là ô ~(i, j)~. Một robot đang ở ô ~(u, v)~ muốn di chuyển về ô góc dưới phải ~(n, n)~ của ma trận.

Yêu cầu

Hãy trả lời ~q~ truy vấn, mỗi truy vấn cho biết số cách di chuyển của robot về ô ~(n, n)~ biết rằng robot chỉ đi được xuống dưới hoặc sang phải. Vì số cách đi là rất lớn nên kết quả được lấy dư cho ~10^9 + 7~.

Dữ liệu đầu vào

Gồm ~q + 1~ dòng:

• Dòng đầu chứa hai số nguyên ~n~ ~(2 \le n \le 10^3)~ và ~q~ ~(1 \le q \le 10^3)~, trong đó ~q~ là số truy vấn;
• ~q~ dòng tiếp theo, dòng thứ ~i~ ~(1 \le i \le q)~ chứa hai số ~u,\ v~ ~(1 \le u, v \le n)~ là vị trí của robot (dòng ~u~, cột ~v~) ở truy vấn ~i~.

Dữ liệu đầu ra

Gồm ~q~ dòng, dòng thứ ~i~ ~(1 \le i \le q)~ là kết quả của truy vấn ~i~.

Ràng buộc dữ liệu

• 10% số điểm có ~n = 2~;
• 20% số điểm có ~n = 3~;
• 20% số điểm có ~q = 1~;
• 20% số điểm có ~2 \le n, q \le 10^2~.

Ví dụ

Ví dụ 1

INPUT

5 3
4 4
4 2
5 5

OUTPUT

2
4
1

Giải thích:

Hình trên mô tả ~2~ cách di chuyển của robot từ ô ~(4, 4)~ về ô ~(5, 5)~.