Cho một tập hợp ~S~ chứa các phần tử là các số nguyên không trùng nhau. Ban đầu ~S~ không chứa phần tử nào.

Bạn cần thực hiện ~Q~ thao tác, mỗi thao tác thuộc ~1~ trong ~3~ loại sau:

• insert(x): Chèn phần tử ~x~ vào trong ~S~ và đưa ra kích cỡ của ~S~ hiện tại;
• count(x): Đưa ra số lượng phần tử ~x~ trong ~S~ (~0~ hoặc ~1~);
• delete(x): Xoá phần tử ~x~ trong ~S~ nếu ~x~ không có trong ~S~.

Input

• Dòng đầu tiên chứa số nguyên dương ~Q~.
• ~Q~ dòng tiếp theo, mỗi dòng chứa ~1~ truy vấn. Mỗi truy vấn được biểu diển thành ~1~ trong ~3~ dạng sau:
  • 0 x: Truy vấn insert(x);
  • 1 x: Truy vấn count(x);
  • 2 x: Truy vấn delete(x).

(~Q \leq 1000, |x| \leq 10^9~)

Output

• In ra các kết quả của truy vấn insert(x) và count(x) trên từng dòng tương ứng khác nhau.

Sample Test

Input:

8
0 1
0 2
0 3
2 2
1 1
1 2
1 3
0 2

Output:

1
2
3
1
0
1
3

Cho một tập hợp ~S~ chứa các phần tử là các số nguyên có thể trùng nhau. Ban đầu ~S~ không chứa phần tử nào.

Bạn cần thực hiện ~Q~ thao tác, mỗi thao tác thuộc ~1~ trong ~3~ loại sau:

• insert(x): Chèn phần tử ~x~ vào trong ~S~ và đưa ra kích cỡ của ~S~ hiện tại;
• count(x): Đưa ra số lượng phần tử ~x~ trong ~S~;
• delete(x): Xoá tất cả phần tử ~x~ trong ~S~.

Input

• Dòng đầu tiên chứa số nguyên dương ~Q~.
• ~Q~ dòng tiếp theo, mỗi dòng chứa ~1~ truy vấn. Mỗi truy vấn được biểu diển thành ~1~ trong ~3~ dạng sau:
  • 0 x: Truy vấn insert(x);
  • 1 x: Truy vấn count(x);
  • 2 x: Truy vấn delete(x).

(~Q \leq 1000, |x| \leq 10^9~)

Output

• In ra các kết quả của truy vấn insert(x) và count(x) trên từng dòng tương ứng khác nhau.

Sample Test

Input:

9
0 1
0 1
0 2
0 3
2 2
1 1
1 2
1 3
0 4

Output:

1
2
3
4
2
0
1
4

Cho một danh sách ~M~ chứa các phần tử tạo bởi ~1~ cặp khoá (có dạng xâu) và giá trị (có dạng số nguyên). ~M~ chỉ được chứa các phần tử có khoá khác nhau, và ban đầu ~M~ không chứa phần tử nào.

Bạn cần thực hiện ~Q~ thao tác, mỗi thao tác thuộc ~1~ trong ~3~ loại sau:

• insert(key, value): Chèn phần tử tạo bởi cặp ~key - value~ vào trong ~M~. Nếu trong ~M~ đã có phần tử với ~key~ cho trước thì thay thế phần tử cũ bằng phần tử mới trên;
• get(key): Đưa ra giá trị của phần tử trong ~M~ với ~key~ đã cho. Nếu không tồn tại phần tử như thế thì in ra ~0~;
• delete(key): Xoá phân tử với ~key~ đã cho.

Input

• Dòng đầu tiên chứa số nguyên dương ~Q~.
• ~Q~ dòng tiếp theo, mỗi dòng chứa ~1~ truy vấn. Mỗi truy vấn được biểu diển thành ~1~ trong ~3~ dạng sau:
  • 0 key value: Truy vấn insert(key, value);
  • 1 key: Truy vấn get(key);
  • 2 key: Truy vấn delete(key).

(~Q \leq 1000, |value| \leq 10^9, key~ là xâu gồm các kí tự chữ cái)

Output

• In ra các kết quả của truy vấn get(x) trên từng dòng tương ứng khác nhau.

Sample Test

Input:

8
0 blue 4
0 red 1
0 white 5
1 red
1 blue
2 red
1 black
1 red

Output:

1
4
0
0

Cho dãy số ~A~ gồm ~N~ phần tử nguyên ~A_1, A_2, A_3, \ldots, A_N~ và một số nguyên ~X~. Hãy đếm xem có bao nhiêu cặp ~(i, j)~ mà ~i < j~ và ~A_i + A_j = X~.

Input

• Dòng đầu tiên chứa số nguyên dương ~N~ và số nguyên ~X~ (~N \leq 10^5~, ~|X| \leq 2 \times 10^9~).
• Dòng thứ hai chứa ~N~ số nguyên của dãy ~A~ (~|A_i| \leq 10^9~).

Output

• In ra số cặp có tổng bằng ~X~ thoả mãn đề bài.

Sample Test

Input:

8 -5
9 -10 5 -5 -7 -4 -14 0

Output:

2

Note:

• 2 cặp thoả mãn là ~(1, 7)~ và ~(2, 3)~.

Cho dãy ~a~ có ~m~ số nguyên ~a_1, a_2, \ldots, a_m~.

Dãy ~b~ có ~n~ số nguyên ~b_1, b_2, \ldots, b_n~. Hãy tìm số lượng phần tử trong dãy ~a~ xuất hiện trong dãy ~b~.

Input

Dòng đầu tiên chứa hai số nguyên ~m~ và ~n~ ~(0 < m, n \leq 10^5)~.

Dòng tiếp theo chứa ~m~ số nguyên ~a_i~ ~(-10^9 \leq a_i \leq 10^9)~.

Dòng tiếp theo chứa ~n~ số nguyên ~b_i~ ~(-10^9 \leq b_i \leq 10^9)~.

Output

Số lượng phần tử trong dãy ~a~ xuất hiện trong dãy ~b~.

Sample

Input

3 5
1 2 3
1 3 3 4 5

Output

2

Bạn được cấp ~N~ khối lập phương theo một thứ tự nhất định và bạn muốn xây dựng các tòa tháp bằng cách sử dụng chúng. Khi hai khối lập phương chồng lên nhau thì khối trên phải nhỏ hơn khối dưới.

Bạn phải xử lý các hình khối theo thứ tự cho trước. Bạn luôn có thể đặt khối lập phương lên trên một tòa tháp hiện có hoặc bắt đầu một tòa tháp mới. Hãy tìm số lượng tháp tối thiểu có thể.

Input

• Dòng đầu tiên chứa số nguyên dương ~N~ - số khối lập phương (~N \leq 2 \times 10^5~).
• Dòng tiếp theo chứa ~N~ số nguyên dương là kích thước của các khối lập phương ~k_1, k_2, k_3, \ldots, k_N~ (~1 \leq k \leq 10^9~).

Output

• In ra số lượng tháp ít nhất.

Sample Test

Input:

5
3 8 2 1 5

Output:

2

Có ~n~ vé hòa nhạc có sẵn, mỗi vé có một mức giá nhất định. Sau đó, ~m~ khách hàng đến, lần lượt đến.

Mỗi khách hàng thông báo mức giá tối đa mà họ sẵn sàng trả cho một vé, và sau đó, họ sẽ nhận được một vé với giá lớn nhất có thể sao cho nó không vượt quá giá tối đa. Vé đó sẽ không còn được bán nữa. Hãy xếp vé cho họ.

Input

• Dòng đầu vào đầu tiên chứa các số nguyên ~n~ và ~m~: số lượng vé và khách hàng.
• Dòng tiếp theo chứa ~n~ số tự nhiên ~h_1, h_2, h_3, \ldots, h_n~ - mức giá của các vé. Các vé có thể có giá bằng nhau.
• Dòng cuối dùng chứa ~m~ số tự nhiên ~t_1, t_2, t_3, \ldots, t_m~ - mức giá tối đa của mỗi khách hàng theo thứ tự họ đến.

Output

• In, đối với mỗi khách hàng, mức giá mà họ sẽ trả cho vé của họ. Sau này, vé không thể được mua lại.
• Nếu khách nào không mua được vé thoả mãn, in ra -1.

Constraints

• ~1 \leq n, m \leq 2 \times 10^5~.
• ~1 \leq h_i, t_i \leq 10^9~.

Sample Test

Input:

5 3
5 3 7 8 5
4 8 3

Output:

3
8
-1

Cho biết danh sách phát của một đài phát thanh kể từ khi thành lập. Danh sách phát có tổng cộng ~N~ bài hát.

Dãy các bài hát liên tiếp dài nhất, mà mỗi bài trong đó đều độc nhất là dãy nào?

Input

• Dòng đầu tiên chứa số tự nhiên ~N~ - số lượng số bài hát.
• Dòng tiếp theo chứa ~N~ số nguyên dương ~k_1, k_2, k_3, \ldots ,k_N~ - mã số của mỗi bài hát.

Output

• In độ dài của dãy dài nhất mà mỗi bài hát là duy nhất.

Constraints

• ~1 \leq N \leq 2 \times 10^5~.
• ~1 \leq k_i \leq 10^9~.

Sample Test

Input:

8
1 2 1 3 2 7 4 2

Output:

5

Cho một dãy số ban đầu rỗng, bạn cần thực hiện ~Q~ thao tác, thao tác thứ ~i~ chèn thêm ~b_i~ số có giá trị ~a_i~ vào cuối dãy số.

Hỏi sau khi thực hiện xong ~Q~ thao tác thì số nhỏ thứ ~K~ trong dãy có giá trị bao nhiêu?

Input

• Dòng đầu tiên chứa số nguyên ~Q~ (~1 \leq Q \leq 10^5~).
• ~Q~ dòng tiếp theo, mỗi dòng ghi hai số nguyên ~a_i~ và ~b_i~ (~1 \leq a_i, b_i \leq 10^9~).
• Dòng cuối cùng chứa số nguyên ~K~ (~K \leq \sum_{i=1}^{Q} b_i~).

Output

• In ra giá trị nhỏ thứ ~K~ sau ~Q~ truy vấn.

Sample Tests

Trên mặt phẳng toạ độ ~Oxy~ có ~N~ điểm màu đỏ và ~N~ điểm màu xanh. Điểm màu đỏ thứ ~i~ có toạ độ ~(a_i, b_i)~ và điểm màu xanh có toạ độ ~(c_i, d_i)~. Tất cả các điểm đều có hoành độ và tung độ phân biệt.

Một điểm đỏ và một điểm xanh có thể tạo thành một cặp thân thiện khi và chỉ khi hoành độ của điểm đỏ nhỏ hơn hoành độ của điểm xanh, và tung độ của điểm đỏ nhỏ hơn tung độ của điểm xanh. Nói cách khác, điểm đỏ thứ ~i~ và điểm xanh thứ ~j~ có thể tạo thành một cặp thân thiện khi và chỉ khi ~a_i < c_j~ và ~b_i < d_j~.

Hãy cho biết có thể tạo tối đa bao nhiêu cặp thân thiện, sao cho mỗi điểm chỉ thuộc tối đa một cặp thân thiện.

Input

• Dòng đầu tiên gồm số nguyên ~N~ (~1 \leq N \leq 10^5~) - số điểm đỏ cũng như số điểm xanh.
• ~N~ dòng tiếp theo, dòng thứ ~i~ gồm hai số nguyên ~a_i~ và ~b_i~ (~10^9 \leq a_i, b_i \leq 10^9~) - toạ độ của điểm đỏ thứ ~i~.
• ~N~ dòng tiếp theo, dòng thứ ~i~ gồm hai số nguyên ~c_i~ và ~d_i~ (~10^9 \leq c_i, d_i \leq 10^9~) - toạ độ của điểm xanh thứ ~i~.

Dữ liệu vào đảm bảo các số nguyên ~a_1, a_2, \ldots, a_N, c_1, c_2, \ldots, c_N~ khác nhau từng dôi một, và các số nguyên ~b_1, b_2, \ldots, b_N, d_1, d_2, \ldots, d_N~ khác nhau từng dôi một.

Output

• In ra một số nguyên duy nhất là số cặp thân thiện tối đa có thể tạo được

Subtasks

• ~25\%~ số test có ~N \leq 8~.
• ~25\%~ số test có ~N \leq 16~.
• ~25\%~ số test có ~N \leq 1000~.
• ~25\%~ số test có ~N \leq 10^5~.

Sample Test 1

Input:

3
-2 -2
-3 1
1 3
2 0
-1 4
3 -1

Output:

2

Sample Test 2

Input:

3
-3 3
-2 2
-1 1
1 -1
2 -2
3 -3

Output:

0

Bạn được cho một mảng gồm n số nguyên, và nhiệm vụ của bạn là tìm hai giá trị (ở hai vị trí khác nhau) có tổng bằng ~x~.

Input

• Dòng đầu tiên của đầu vào chứa hai số nguyên ~n~ và ~x~: kích thước của mảng và tổng mục tiêu.
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~: các giá trị của mảng.

Output

• In ra hai số nguyên: vị trí của các giá trị. Nếu có nhiều lời giải, bạn có thể in ra bất kỳ lời giải nào. Nếu không có lời giải, in ra IMPOSSIBLE.

Constraints

• ~1 \leq n \leq 2\times10^5~
• ~1 \leq x, a_i \leq 10^9~

Sample Test

Input:

4 8
2 7 5 1

Output:

2 4

Bạn được cho một mảng gồm ~n~ số nguyên và nhiệm vụ của bạn là tìm bốn giá trị (tại các vị trí phân biệt) có tổng là ~x~.

Input

• Dòng đầu vào đầu tiên có hai số nguyên ~n~ và ~x~ - kích thước mảng và tổng mong muốn.
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~ - các giá trị của mảng.

Output

• In ba số nguyên: vị trí của các giá trị. Nếu có một số lời giải, bạn có thể in bất kỳ lời giải nào trong số đó. Nếu không có lời giải nào, in ~IMPOSSIBLE~.

Constraints

• ~1 \leq n \leq 1000~
• ~1 \leq x, a_i \leq 10^9~.

Sample Test

Input:

8 15
3 2 5 8 1 3 2 3

Output:

2 4 6 7