Quốc tế Thiếu nhi 2022

Nhân ngày Quốc tế thiếu nhi, tụi mình gửi đến các bạn một trò chơi tuổi thơ mà ai cũng đã từng chơi.

Một người nông dân muốn qua sông cùng với các vật phẩm của mình, bao gồm \(A\) con sói, \(B\) con cừu và \(C\) củ bắp cải. Ông có thể lái đò chở các vật phẩm của mình qua sông, và mỗi lần chở được tối đa \(K\) vật phẩm cùng một lúc, không tính người nông dân. Nói cách khác, ở mỗi lần chở, người nông dân có thể đưa một số vật phẩm từ bờ sông này qua bờ sông bên kia và có thể đi ngược về.

Tuy nhiên, khi không có mặt người nông dân, sói sẽ ăn cừu, cừu sẽ ăn bắp cải (nhưng sói không ăn bắp cải). Khi có mặt người nông dân, mọi nhóm vật phẩm đều thỏa mãn (kể cả trên bờ và trên đò). Người nông dân không muốn mất vật phẩm của mình, vì vậy ông muốn nghĩ ra một lộ trình đưa đò để không có vật phẩm nào bị mất đi. Ông ấy không giỏi tính toán, do đó bạn hãy giúp người nông dân kiểm tra xem liệu ông ấy có thể qua sông với đầy đủ vật phẩm không nhé.

Input

• Một dòng chứa 4 số nguyên dương \(A, B, C, K\). \(\ (0 \leq A, B, C, K \leq 10^6, \ 1 \leq max(A, B, C))\)

Output

• In ra YES nếu tồn tại cách đưa đò để người nông dân và tất cả vật phẩm đều qua được sông. Ngược lại, in ra NO nếu không có cách đi.

Example

1 1 1 1

YES

2 2 0 1

NO

Cho ba số \(a, b, c\). Hãy đếm số lượng số nguyên dương không lớn hơn \(n\) sao cho số đó chia hết cho một trong ba số \(a, b, c\).

Input

• Gồm một dòng duy nhất chứa bốn số lần lượt là \(n, a, b\) và \(c\) \((1 \leq a, b, c \leq n \leq 10^{12})\).

Output

• Gồm một số duy nhất số lượng số thỏa mãn đề.

Scoring

• Subtask \(1\) (\(60\%\) số điểm): \(n \leq 10^{6}\).
• Subtask \(2\) (\(40\%\) số điểm): không có rằng buộc gì thêm.

Example

Có \(n\) người trong một cuộc thi, họ hoàn toàn không quen nhau.

Cuộc thi diễn ra trong \(n\) giờ, và trong quãng thời gian đó, cứ mỗi giờ thứ \(i\) thì game bắt đầu lại từ đầu, và lại có một yêu cầu mới được đặt ra: \(i-1\) yêu cầu trước phải thỏa mãn, và người thứ \(x_i\) và người thứ \(y_i\) phải quen nhau.

Hai người \(x, y\) được gọi là quen nhau nếu họ trực tiếp làm quen với nhau, hoặc có một dãy \(p_1 = x, p_2, p_3, \dots, p_k = y\) mà với mọi \(i < k\) thì người \(p_i\) quen người \(p_{i+1}\).

Bạn là thành viên ban tổ chức, với nhiệm vụ là sau mỗi giờ, bạn phải sắp xếp lại các cặp người quen trực tiếp, sao toàn bộ cho các điều kiện tới thời điểm đó đều thỏa mãn.

Sau mỗi giờ từ giờ thứ nhất tới giờ thứ \(n\), hãy cho biết số người quen trực tiếp nhiều nhất mà một người có thể quen tại thời điểm đó là bao nhiêu.

Input

• Dòng đầu tiên chứa hai số \(n, d\). \((2 \le n \le 2 \times 10^5, 1 \le d \le n-1)\)
• \(d\) dòng sau, dòng thứ \(i\) chứa hai số \(x_i, y_i\) biểu thị hai người chưa quen với nhau trước giờ thứ \(i\).

Output

In ra \(d\) dòng, dòng thứ \(i\) biểu thị đáp án sau giờ thứ \(i\).

Scoring

• Subtask 1 (40%): \(n \le 2 \times 10^3\)
• Subtask 2 (60%): \(n \le 2 \times 10^5\)

Example

Bé An vừa mới mua một con quay, và chơi trong một tiếng đồng hồ. Bỗng, bé nghĩ ra một ý tưởng thật (không) lạ, đó là một bảng lốc xoáy.

Bảng này gồm có \(m\) hàng và \(n\) cột. Chúng ta điền số \(1\) từ góc trái trên, sau đó điền lần lượt từ ngoài vào trong theo chiều kim đồng hồ. Có thể xem hình dưới để tham khảo.

Bé An muốn biết số nhỏ nhất và số lớn nhất của từng hàng. Các bạn hãy giúp An nhé!

Input

• Gồm một dòng duy nhất chứa hai số nguyên dương \(m\) và \(n\) \((1 \leq m, n \leq 10^{6})\).

Output

• In ra \(m\) dòng, dòng thứ \(i\) in ra hai số, lần lượt là số nhỏ nhất và lớn nhất của hàng thứ \(i\).

Scoring

• Subtask \(1\) (\(60\%\) số điểm): \(m, n \leq 10^{3}\).
• Subtask \(2\) (\(40\%\) số điểm): không có rằng buộc gì thêm.

Example

5 6

1 6
7 22
8 30
9 27
10 15

Bạn An có một bí mật rất lớn, nên chỉ có \(3\) người bạn tên là \(X, Y, Z\) được phép biết. Để đảm bảo sự bảo mật, An tạo ra một loại mật mã gần giống RSA: An tạo ra \(4\) chiếc khóa, một chiếc khóa tổng có số \(n\) là tích của ba số trên ba chiếc còn lại. An đem ba chiếc khóa đó tặng cho ba bạn.

An đã làm xong chiếc khóa của mình, và tự hỏi mình có bao nhiêu cách làm khóa? Hai cách làm khóa được gọi là khác nhau nếu tồn tại một bạn nhận được hai chìa khóa khác nhau trong hai cách.

Bạn hãy tính giúp An nhé!

Input

• Chứa một số duy nhất là số \(n\) \((1 \leq n \leq 10^{15})\) trên chìa khóa tổng.

Output

• Gồm một số duy nhất là số cách làm khóa cho ba bạn.

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(n \leq 500\).
• Subtask \(2\) (\(30\%\) số điểm): \(n \leq 10^{6}\).
• Subtask \(3\) (\(15\%\) số điểm): \(n \leq 10^{12}\).
• Subtask \(4\) (\(15\%\) số điểm): không có rằng buộc gì thêm.

Example