Thi thử 15

Cho số tự nhiên \(n\). Viết chương trình tính tổng:

Input

• Gồm một dòng duy nhất ghi số tự nhiên \(n\) (\(2 \leq n \leq 10^{20}\)).

Output

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

Example

3   

30

5  

210

Giả thuyết Goldbach do nhà toán học người Đức Christian Goldbach(1690 - 1764) nêu ra vào năm 1742 trong lá thư gửi tới Leonhard Euler, là một trong những bài toán lâu đời và nổi tiếng còn chưa có giải được trong lý thuyết số nói riêng và toán học nói chung.

Giả thuyết phỏng đoán rằng: "Mỗi số tự nhiên chẵn lớn hơn 2 có thể biểu diễn bằng tổng của hai số nguyên tố".

Viết chương trình để kiểm tra kết quả phỏng đoán của Goldbach.

Input

• Dòng đầu tiên ghi số tự nhiên \(n\) (\(n < 200\)) là số test cần kiếm tra.
• \(n\) dòng tiếp theo, mỗi dòng ghi một số tự nhiên chẵn \(k\) (\(2 < k \leq 10^{12}\)).

Output

• Gồm \(n\) dòng, mỗi dòng tương ứng với một test. Trên mỗi dòng, ghi hai số nguyên tố có tổng bằng số đã cho tương ứng, hai số ghi theo thứ tự tăng dần và cách nhau một khoảng trắng, nếu có nhiều kết quả thì ghi hai số có giá trị tuyệt đối của hiệu lớn nhất hoặc ghi "NO" nếu không tìm được.

Example

2
14
24 

3 11
5 19

Cho dãy số \(A\) gồm \(N\) phần tử là các số nguyên dương \(a_1, a_2,..., a_n\). Thực hiện lần lượt \(Q\) thao tác trên dãy số đó, thao tác thứ i sẽ có một trong hai loại như sau:

• Loại 1: \(1 \ p_i \ m_i \ x_i\) tăng giá trị phần tử tại vị trí \(p_i\) tới vị trí \(m_i\) của dãy số \(A\) thêm \(x_i\) đơn vị.
• Loại 2: \(2 \ u_i \ v_i\) tính tổng các phần tử của dãy số \(A\) từ vị trí \(u_i\) tới vị trí \(v_i\).

Viết chương trình thực hiện \(Q\) thao tác trên và ghi ra kết quả của các thao tác Loại \(2\).

Input

• Dòng đầu tiên ghi hai số nguyên dương \(N, Q\) (\(1 \leq N, Q \leq 10^5\)).
• Dòng thứ hai là một dãy số gồm \(N\) số nguyên dương (\(0 < a_i \leq 10^9\)), các số nằm trên một dòng và cách nhau một khoảng trắng.
• \(Q\) dòng tiếp theo (từ dòng thứ 3 trở đi), với dòng thứ \(i\) số đầu tiên là \(1\) hoặc \(2\):
  • Nếu số \(1\) thì theo sau là ba số nguyên dương \(p_i, m_i\) và \(x_i\) (\(1 \leq p_i \leq m_i \leq N, 1 \leq x_i \leq 10^9\)). Các số nằm trên một dòng và cách nhau một khoảng trắng.
  • Nếu số \(2\) thì theo sau là hai số nguyên dương \(u_i\) và \(v_i\) (\(1 \leq u_i \leq v_i \leq N\)). Các số nằm trên một dòng và cách nhau một khoảng trắng.

Output

• Gồm \(n\) dòng, mỗi dòng ghi kết quả tương ứng với thao tác Loại 2.

Example

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

98
137

Trong một chương trình nghệ thuật diễn ra liên tục trong \(n\) giờ, Công ty X có danh sách của \(m\) nghệ sĩ khác nhau có thể thuê để biểu diễn. Thời điểm bắt đầu biểu diễn được tính bằng \(0\). Để đơn giản trong quản lý và sắp xếp, các nghệ sĩ được đánh số theo thứ tự từ \(1\) tới \(m\), nghệ sĩ thứ \(i\) (với \(i = 1, 2, ..., m\)) biểu diễn trong thời điểm \(s_i\) đến thời điểm \(t_i\) (\(0 \leq s_i < tᵢ \leq n\)) với tiền công là \(c_i\) (\(0 \leq c_i \leq 10^6\)).

Viết chương trình thuê các nghệ sĩ để bất cứ thời điểm nào cũng luôn có ít nhất một nghệ sĩ biểu diễn đồng thời chi phí thuê là nhỏ nhất.

Input

• Dòng đầu tiên chứa 2 số nguyên \(n\) và \(m\) (\(0 < n, m \leq 100\)).
• \(m\) dòng tiếp theo, mỗi dòng chứa ba số nguyên không âm \(s_i, t_i\) và \(c_i\), các số nằm trên một dòng và cách nhau một khoảng trắng.

Output

• Một số nguyên là chi phí thuê nhỏ nhất (dữ liệu được cho đảm bảo luôn có kết quả).

Example

9 5
0 5 25
1 3 18
3 7 21
4 6 38
7 9 20

66