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

Conan đang trong một vụ án cực kì hóc búa, đã có đến 2 vụ án mạng xảy ra. Tại hiện trường 2 vụ án đều để lại dòng chữ kì lạ. Có vẻ như đó chính là gợi ý mà hung thủ để lại. Hung thủ dường như đang cố thách thức vị thám tử lừng danh của chúng ta. Bằng tài năng suy luận tài tình của mình, Conan đã khám phá đã ra được gợi ý của hung thủ chính là sự tương đồng của 2 dòng chữ đó. Tuy nhiên các dòng chữ rất dài, Conan giỏi suy luận nhưng lại không giỏi lập trình. Bạn là một lập trình viên giỏi, bạn hãy giúp Conan nhé.

Yêu cầu: Cho 2 chuỗi kí tự \(a\) và \(b\). Hãy xác định xem chuỗi \(a\) và \(b\) giống nhau bao nhiêu kí tự?

Input

• Dòng thứ nhất là chuỗi kí tự \(a (1 \leq |a| \leq 10^{5})\).
• Dòng thứ hai là chuỗi kí tự \(b\) \((1 \leq |b| \leq 10^{5})\).
• Các chuỗi chỉ gồm các kí tự từ \(\texttt{a}\) \(\rightarrow\) \(\texttt{z}\), \(|x|\) là số lượng ký tự của chuỗi \(x\).

Output

• Gồm một dòng duy nhất là số lượng kí tự giống nhau.

Example

aaabb
baa

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

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

In ra tất cả cặp số nguyên tố \(A,B(A\le B)\) thỏa mãn \(A+B\) cũng là số nguyên tố và \(A+B\le N\).

Input

• Dòng thứ nhất chứa số nguyên dương \(N(1\le N\le 10^6)\)

Output

• Dòng thứ nhất in ra số \(k\) - số lượng cặp \((A,B)\) thỏa mãn yêu cầu bài toán

• In ra \(k\) cặp \((A,B)\) thỏa mãn yêu cầu bài toán (theo thứ tự từ điển từ bé đến lớn).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(0<N\le 10\)

• Subtask \(2\) (\(20\%\) số điểm): \(0<N\le 10^4\)

• Subtask \(3\) (\(60\%\) số điểm): Không có yêu cầu gì thêm.

Example

7

2
2 3
2 5

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

Cho \(N\) số nguyên dương \(a_1, a_2, a_3, \ldots, a_N\). Hãy đếm xem có bao nhiêu bộ chỉ số \((i, j)\) (\(1 \leq i, j \leq N\)) sao cho thương của \(a_i\) chia cho \(a_j\) là một số nguyên tố.

Input

• Dòng đầu tiên gồm một số nguyên dương \(N\) (\(N \leq 10^5\)).
• Dòng tiếp theo gồm \(N\) số nguyên dương \(a_i\) (\(a_i \leq 10^6; 1 \leq i \leq N\)).

Output

• In ra kết quả của bài toán.

Subtasks

• Subtask 1 (\(30\%\) số điểm đầu): \(N \leq 10^3\).
• Subtask 2 (\(30\%\) số điểm tiếp): Tất cả \(a_i \leq 10^3\).
• Subtask 3 (\(40\%\) số điểm còn lại): Không có ràng buộc gì thêm.

Sample Test

6
2 3 4 15 10 15

4

```

Uesugi Tèo - một coder nổi tiếng trong đội tuyển Tin Ams, đã được gia đình nhà Nakano giàu có thuê làm gia sư Tin học dạy kèm con họ. Lạ thay, những đứa con của gia đình nọ là những người chị em sinh năm học cùng khối với cậu trên trường. Bằng quyết tâm và nhiệt huyết với việc giúp 5 chị em họ vượt qua bài kiểm tra của thầy Tùng, Uesugi đã giao mỗi người một bài toán phù hợp với năng lực của họ, với phần thưởng đi kèm là một chuyến dã ngoại cùng cậu. Sau khi đắn đo suy nghĩ, cậu giao cho Nino Nakano bài toán như sau:

Nino được cho \(N\) số nguyên dương \(a_1, a_2, \dots, a_N\) và một số nguyên dương \(K\). Cô được yêu cầu chọn ra một dãy các vị trí \(i_1, i_2, \dots, i_M \ (1 \leq M \leq N)\) trong số \(N\) vị trí ban đầu, sao cho trong những vị trí được chọn, không tồn tại hai vị trí \(i_x, i_y \ (i_x \neq i_y)\) thỏa mãn \(a_{i_x} \times a_{i_y}\) là một lũy thừa bậc \(K\). Ví dụ, với \(K = 2\) và \(a = \{1, 2, 8, 16, 3, 9\}\), Nino có thể chọn tập \(\{1, 2, 5\}\) hoặc \(\{4\}\), nhưng không thể chọn đồng thời vị trí \((1, 4)\), hay \((4, 6)\). Để làm bài toán khó hơn, Uesugi yêu cầu Nino tìm dãy con lớn nhất thỏa mãn điều kiện trên. Nếu không tồn tại đoạn thỏa mãn, Nino cần trả về -1.

Nino không muốn trông cậy vào sự giúp đỡ của Uesugi, nên bạn được yêu cầu giải bài toán này nhanh nhất có thể để không làm phật lòng Uesugi cũng như những người chị em của cô.

Input

• Dòng đầu tiên nhập vào hai số nguyên dương \(N, K \ (1 \leq N \leq 2 \times 10^5, \ 2 \leq K \leq 5)\).
• Dòng tiếp theo nhập vào \(N\) số nguyên dương \(a_1, a_2, \dots, a_N \ (1 \leq a_i \leq 2 \times 10^6)\) được ngăn bởi dấu cách.

Output

• In ra một số nguyên duy nhất là kết quả của bài toán hoặc -1 nếu không tồn tại dãy thỏa mãn.

Scoring

• Subtask 1 \((7p)\): \(N \leq 14\).
• Subtask 2 \((13p)\): \(N \leq 20\).
• Subtask 3 \((11p)\): \(K = 2, \ N \leq 2000\).
• Subtask 4 \((16p)\): \(N \leq 2000\).
• Subtask 5 \((22p)\): \(K = 2\).
• Subtask 6 \((31p)\): Không có ràng buộc gì thêm.

Sample Input 1

6 2
1 2 8 16 3 9

Sample Ouput 1

3

Notes

• Chọn các số \(\{1, 3, 5\}\).