Tudor đang ngồi trong lớp học, thế nhưng anh ta lại không chú ý vào bài học. Thế nhưng anh ấy bị giáo viên Toán gọi lên bảng để làm một số bài tập. Vì giáo viên không mong đợi gì quá nhiều ở Tudor nên anh ấy chỉ cần làm bài toán cộng đơn giản. Tuy bài toán có thể dễ với bạn nhưng không dễ với Tudor, vì vậy hãy giúp anh ấy !!

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) \((n \le 100\, 000)\) - số bộ dữ liệu vào.
• \(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên có giá trị tuyệt đối không quá \(1\,000\,000\,000\), cách nhau bởi một dấu cách.

Output

• Ứng với mỗi bộ dữ liệu, in ra kết quả của bài toán tính tổng.

Example

2
1 1
-1 0 

2
-1

Cho một dãy gồm \(N\) số nguyên dương \(A_1, A_2,…, A_N\).(\(N ≤ 10^4, A_i ≤ 10^9\)) và số \(K\) (\(K ≤ N\)). Hãy in ra số nhỏ thứ \(K\) trong dãy.

Input

• Dòng đầu chứa số \(N, K\),
• Dòng thứ hai chứa \(N\) số nguyên dương \(A_1, A_2,…, A_N\).

Output

• Một dòng chứa dãy số nhỏ thứ \(K\) trong dãy.

Example

6 4    
91 451 43 3 452 54 

91

Một lớp học nọ của Boss Small có \(N\) học sinh. Một ngày đẹp trời, Boss Small nhận thấy số học sinh đi học chỉ có \(M\) người, ít hơn \(N\) nên Boss quyết định nhờ bạn điểm danh các học sinh trong lớp. Hãy viết một chương trình cho biết số thứ tự của các học sinh vắng mặt theo thứ tự tăng dần.

Biết rằng, lớp học đánh số thứ tự cho học sinh từ \(1\) cho đến \(N\).

Input

• Dòng đầu tiên chứa hai số nguyên dương lần lượt là \(N\) và \(M\) \((1 \leq M < N \leq 10^5)\)
• Dòng thứ hai chứa \(M\) số nguyên khác nhau từng đôi một, có giá trị trong đoạn \([1, N]\).

Output

• In ra một danh sách các số nguyên, là số thứ tự của những học sinh vắng mặt, theo thứ tự tăng dần.

Example

5 3
5 2 3 

1 4

2 1
2 

1

ami có \(n\) món đồ chơi. Món đồ chơi thứ \(i\) có màu \(c[i]\). Hôm nay, khi đem kho đồ chơi ra ngắm thì ami phát hiện thấy thiếu mất \(m\) món. Hãy tìm màu sắc của \(m\) món đồ chơi bị mất đó.

Input

• Dòng đầu tiên chứa hai số nguyên \(n, m \ (3 \leq n \leq 10^5, 1 \leq m \leq 2)\).
• Dòng thứ hai chứa \(n\) số nguyên dương \(c[i] \ (1 \leq c[i] \leq 10^5)\). Lưu ý, có thể có nhiều món đồ chơi có cùng màu
• Dòng thứ ba chứa \((n - m)\) số nguyên dương, là màu của các món đồ không bị mất.

Output

• In ra \(m\) số nguyên theo thứ tự tăng dần, là màu các món đồ chơi bị mất.

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(n \leq 100, m = 1\)
• Subtask \(2\) (\(25\%\) số điểm): \(n \leq 10^5, m = 1\)
• Subtask \(3\) (\(25\%\) số điểm): \(n \leq 100, m = 2\)
• Subtask \(4\) (\(25\%\) số điểm): \(n \leq 10^5, m = 2\)

Example

3 1
1 3 2
1 2

3

4 2
2 2 2 4
2 4

2 2

3 2
1 2 3
2

1 3

Cho một dãy gồm \(n\) số nguyên dương \(a_1,a_2,…,a_n\). Một hàm \(f\) được định nghĩa như sau:

\(f(x)=x*count_a (x)\)

với \(count_a (x)\) là số lần xuất hiện của \(x\) có trong dãy \(a\).

Yêu cầu: Hãy tìm phần tử \(a_i\) có \(f(a_i )\) lớn nhất \((1\le i\le n)\).

Input

• Dòng đầu tiên là số nguyên dương \(n (n\le 10^5 )\).
• Dòng thứ hai gồm n số nguyên dương \(a_1,a_2,…,a_n (a_i\le 10^9)\).

Output

• In ra phần tử \(a_i\) có \(f(a_i )\) lớn nhất \((1\le i\le n)\). Nếu có nhiều kết quả thỏa mãn, in ra kết quả lớn nhất.

Scoring

• 80% test: \(n\le 10^3,a_i\le 10^6\)
• 20% test: không có ràng buộc

Example

5
1 2 3 4 5

5

4
1 2 1 1

1

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 một 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 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ố. Trong bài toán này bạn được cho một số tự nhiên chẵn \(n\), bạn hãy đếm số lượng cặp số nguyên tố \(a , b (a ≤ b)\) mà \(a + b = n\).

Input

• Gồm một dòng chứa một số tự nhiên chẵn \(n\).

Output

• Gồm dòng chứa một số là số lượng cặp số nguyên tố \(a , b\) mà \(a ≤ b\) và \(a + b = n\)

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n ≤ 10^3\).
• Subtask \(2\) (\(50\%\) số điểm): \(n ≤ 10^6\).

Example

10 

2

Cho một tập hợp rỗng, bạn sẽ lần lượt thực hiện N thao tác. Có hai loại thao tác được thực hiện:

• Thao tác 1 có dạng (1, \(x\)) : thêm số \(x\) vào tập hợp.
• Thao tác 2 có dạng (2, \(x\)): loại bỏ một số \(x\) ra khỏi tập hợp, dữ liệu luôn đảm bảo tồn tại ít nhất một số \(x\) trước khi thực hiện thao thao tác này.

Sau mỗi lần thực hiện thao tác, hãy đưa ra ước chung lớn nhất của tập hợp này. Với trường hợp tập hợp con rỗng hãy in ra số 1, tập hợp có một phần tử thì in ra phần tử đó.

Input

• Dòng đầu tiên một số tự nhiên \(N\) (\(1 \leq N \leq 1000\)).
• \(N\) dòng tiếp theo, mỗi dòng là gồm 2 số \(t\) và \(x\) với \(t\) là loại thao tác và \(x\) là số cần được xử lí (\(1 \leq t \leq 2\), \(1 \leq x \leq 10^{9}\)).

Output

• Gồm \(N\) dòng là ước chung lớn nhất của tập hợp sau mỗi lần thực hiện một thao tác.

Example

6  
1 8     
1 12     
1 10     
1 8     
2 8     
2 8 

8     
4     
2     
2     
2     
2

Trong Quảng trường 2/9 có một đài phun nước được thiết kế rất đặc biệt. Đài phun có bốn vòi phun được bố trí tại bốn đỉnh của một hình vuông. Lịch phun nước của các vòi được điều khiển bằng một chương trình tự động. Tại thời điểm bắt đầu, các vòi sẽ bắt đầu phun, vòi thứ \(i\) sẽ phun nước trong thời gian \(T_i\ (i=1 \rightarrow 4)\) phút và ngưng phun \(x\) phút. Các vòi phun lặp lại theo quy trình trên. Thời điểm đẹp nhất là lúc cả 4 vòi cùng bắt đầu phun. Minh đến Quảng trường tại thời điểm \(S\) thì sau bao nhiêu phút nữa sẽ gặp thời điểm đẹp nhất của đài phun nước.

Yêu cầu: Cho \(T_1,T_2,T_3,T_4,x\) và \(S\), hãy tính thời gian chờ ít nhất của bạn Minh để gặp thời điểm đẹp nhất.

Dữ liệu: Nhập từ bàn phím

• Dòng thứ nhất chứa 4 số nguyên dương \(T_1,T_2,T_3,T_4\)
• Dòng thứ hai chứa số hai nguyên dương \(x,S (x \le 10000; S≤10^{16})\).

Kết quả: Ghi ra màn hình

• Thời gian chờ ít nhất

Ràng buộc:

• 60% tests tương ứng 60% số điểm có \(T_1,T_2,T_3,T_4≤100\)
• 40% tests tương ứng 40% số điểm có \(T_1,T_2,T_3,T_4≤10000\)

Ví dụ

2 3 1 2
1 6

6