Cho một dãy ~A~ gồm các số nguyên có giá trị tuyệt đối nhỏ hơn ~10^9~, đánh số từ ~0~. Ban đầu dãy 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:

• push_back(x): Đẩy số nguyên ~x~ vào cuối dãy ~A~;
• at(x): Đưa ra số ở vị trí ~x~ trong dãy ~A~;
• pop_back(): Xoá số ở cuối dãy ~A~.

Input

• Dòng đầu tiên chứa số nguyên dương ~Q~ (~Q \leq 1000~).
• ~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 push_back(x);
  • 1 x: Truy vấn at(x). Đảm bảo x luôn nhỏ hơn kích cỡ hiện tại của dãy;
  • 2: Truy vấn pop_back(). Đảm bảo dãy luôn có phần tử trước truy vấn này.

Output

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

Sample Test

Input:

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

Output:

1
2
4

Cho ~N~ thùng sách được đánh số từ ~1~ đến ~N~. Ban đầu các thùng sách không chứa quyển sách nào.

Bạn cần thực hiện ~Q~ công việc, mỗi công việc thuộc ~1~ trong ~3~ loại sau:

• push(t, x): Cho quyển sách có tiêu đề x lên đầu thùng sách thứ t;
• top(t): Đưa ra tiêu đề của cuốn sách ở đầu thùng sách thứ t;
• pop(t): Bỏ quyển sách ở đầu thùng sách thứ t ra ngoài. Nếu thùng không có sách thì bỏ qua.

Input

• Dòng đầu tiên chứa 2 số nguyên dương ~N, Q~.
• ~Q~ dòng tiếp theo, mỗi dòng chứa ~1~ công việc. Mỗi công việc được biểu diển thành ~1~ trong ~3~ dạng sau:
  • 0 t x: Biểu diễn công việc push(t, x);
  • 1 t: Biểu diễn công việc top(t), đảm bảo thùng sách t có sách.
  • 2 t: Biểu diễn công việc pop(t).

(~N, Q \leq 1000, t \leq N, x~ là xâu độ dài không quá ~1000~ kí tự chữ cái và số)

Output

• In ra tên các quyển sách trong các công việc top(t) trên từng dòng khác nhau.

Sample Test

Input:

3 9
0 1 100BaiSTLChoThieuNhiTap1
0 1 100BaiSTLChoThieuNhiTap2
0 1 100BaiSTLChoThieuNhiTap3
0 2 100BaiSTLChoThieuNhiTap4
0 3 100BaiSTLChoThieuNhiTap5
1 1
1 3
2 1
1 1

Output:

100BaiSTLChoThieuNhiTap3
100BaiSTLChoThieuNhiTap5
100BaiSTLChoThieuNhiTap2

Một cửa hàng pizza đang muốn tăng hiệu suất bán hàng để tiếp nhận được nhiều khách hơn. Vì vậy, ở quầy bán hàng, họ đã chia ra thành ~N~ hàng để điều phối khách mua. Các hàng được đánh số từ ~1~ đến ~N~. Ban đầu các hàng chưa có khách nào đứng.

Bạn là một bảo vệ ở đó, và cần thực hiện ~Q~ công việc, mỗi công việc thuộc ~1~ trong ~3~ loại sau:

• push(t, x): Dẫn khách tên ~x~ vào cuối hàng ~t~;
• top(t): Đọc tên khách hàng ở đầu hàng ~t~;
• pop(t): Dẫn khách ở đầu hàng ~t~ ra ngoài. Nếu hàng không có khách thì bỏ qua.

Input

• Dòng đầu tiên chứa 2 số nguyên dương ~N, Q~.
• ~Q~ dòng tiếp theo, mỗi dòng chứa ~Q~ công việc. Mỗi công việc được biểu diển thành ~1~ trong ~3~ dạng sau:
  • 0 t x: Biểu diễn công việc push(t, x);
  • 1 t: Biểu diễn công việc top(t);
  • 2 t: Biểu diễn công việc pop(t).

(~N, Q \leq 1000, t \leq N, x~ là xâu độ dài không quá ~1000~ kí tự chữ cái)

Output

• In ra các tên khách hàng đã đọc ở công việc top(x) trên các dòng tương ứng khác nhau.

Sample Test

Input:

3 9
0 1 An
0 1 Binh
0 1 Cuong
0 3 Dung
0 3 Giang
1 1
1 3
2 1
1 1

Output:

An
Dung
Binh

Cho một dãy ~A~ gồm các số nguyên, đánh số từ ~0~. Ban đầu dãy 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:

• push(t, x): Đẩy số nguyên ~x~ vào đầu dãy ~A~ (nếu ~t = 0~) hoặc cuối dãy ~A~ (nếu ~t = 1~);
• at(x): Đưa ra số ở vị trí ~x~ trong dãy ~A~;
• pop(t): Xoá số ở đầu dãy ~A~ (nếu ~t = 0~) hoặc cuối dãy ~A~ (nếu ~t = 1~).

Input

• Dòng đầu tiên chứa số nguyên dương ~Q~ (~Q \leq 1000~).
• ~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 t x: Truy vấn push(t, x);
  • 1 x: Truy vấn at(x). Đảm bảo x luôn nhỏ hơn kích cỡ hiện tại của dãy;
  • 2 t: Truy vấn pop(t). Đảm bảo dãy luôn có phần tử trước truy vấn này.

Output

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

Sample Test

Input:

11
0 0 1
0 0 2
0 1 3
1 0
1 1
1 2
2 0
2 1
0 0 4
1 0
1 1

Output:

2
1
3
4
1

Một cửa hàng pizza đang muốn tăng hiệu suất bán hàng để tiếp nhận được nhiều khách hơn. Vì vậy, ở quầy bán hàng, họ đã chia ra thành ~N~ hàng để điều phối khách mua. Các hàng được đánh số từ ~1~ đến ~N~. Ban đầu các hàng chưa có khách nào đứng.

Tuy nhiên chủ cửa hàng lại có tính thiên vị: Ai nhiều tiền hơn thì sẽ được phục vụ trước.

Bạn là một bảo vệ ở đó, và cần thực hiện ~Q~ công việc, mỗi công việc thuộc ~1~ trong ~3~ loại sau:

• push(t, x): Dẫn khách có số tiền ~x~ vào cuối hàng ~t~.
• top(t): Đọc và ghi lại số tiền của khách hàng giàu nhất ở hàng ~t~.
• pop(t): Dẫn khách giàu nhất ở hàng ~t~ ra ngoài. Nếu hàng không có khách thì bỏ qua. Nếu hàng có nhiều khách cùng số tiền thì chỉ dẫn ~1~ khách ra (bạn đã biết khách nào đã lấy hàng để dẫn ra).

Input

• Dòng đầu tiên chứa 2 số nguyên dương ~N, Q~.
• ~Q~ dòng tiếp theo, mỗi dòng chứa ~Q~ công việc. Mỗi công việc được biểu diển thành ~1~ trong ~3~ dạng sau:
  • 0 t x: Biểu diễn công việc push(t, x).
  • 1 t: Biểu diễn công việc top(t).
  • 2 t: Biểu diễn công việc pop(t). Đảm bảo hàng luôn có khách trước truy vấn này.

(Các số nhập vào đều là số nguyên dương, ~N, Q, x \leq 1000, t \leq N~)

Output

• In ra các số tiền đã ghi lại ở công việc top(x) trên các dòng khác nhau.

Sample Test

Input:

2 10
0 0 3
0 0 9
0 0 1
1 0
2 0
1 0
0 0 4
1 0
0 1 8
1 1

Output:

9
3
4
8

Một thao tác xoay trái dãy là đưa tất cả các phần tử trong dãy sang bên trái một ví trí, còn phần tử đầu tiên xuống cuối dãy.

Cho một dãy ~A~ gồm ~N~ số nguyên dương, hãy đưa ra dãy sau khi xoay trái dãy ~M~ lần.

Input

• Dòng đầu tiên chứa ~2~ số nguyên dương ~N~ và ~M~ (~N, M \leq 10^6~).
• Dòng thứ hai chứa ~N~ số nguyên dương ~A_1, A_2, A_3, \ldots, A_N~ - các phần tử trong dãy ~A~ (~|A_i| \leq 10^9~).

Output

• In ra dãy ~A~ sau ~M~ thao tác xoay trái dãy.

Ví dụ

Input:

5 4
1 2 3 4 5

Output:

5 1 2 3 4

Điều kiện thoả mãn dãy ngoặc đúng được định nghĩa như sau:

• Dãy rỗng "" là một dãy ngoặc đúng.
• Nếu dãy ~A~ là một dãy ngoặc đúng thì ~(A)~ là một dãy ngoặc đúng.
• Nếu dãy ~A~ và dãy ~B~ là hai dãy ngoặc đúng thì ~A + B~ là một dãy ngoặc đúng.

Cho xâu ~s~ là một dãy ngoặc chỉ gồm 2 kí tự là ~(~ và ~)~, hãy kiểm tra xem xâu ~s~ có phải một dãy ngoặc đúng hay không.

Input

• Gồm một dòng chứa xâu ngoặc ~s~ ~(1 \le |s| \le 10^3)~.

Output

• In ra Yes nếu xâu ~s~ là dãy ngoặc đúng, ngược lại in ra No.

Ví dụ

Input 1:

(()())

Output 1:

Yes

Input 2:

(()))

Output 2:

No

Điều kiện thoả mãn dãy ngoặc đúng gồm 2 loại ngoặc ( ) và [ ] được định nghĩa như sau:

• Dãy rỗng "" là một dãy ngoặc đúng.
• Nếu dãy ~A~ là một dãy ngoặc đúng thì ~(A)~ và ~[A]~ là các dãy ngoặc đúng.
• Nếu dãy ~A~ và dãy ~B~ là hai dãy ngoặc đúng thì ~A + B~ là một dãy ngoặc đúng.

Cho xâu ~s~ là một dãy ngoặc gồm ~2~ loại ngoặc như trên (~4~ loại kí tự). Nếu xâu ~s~ là một dãy ngoặc đúng, với mỗi kí tự của ~s~, in ra số thứ tự của ngoặc tương ứng với nó. Nếu không, in ra ~-1~. Các kí tự được đánh số từ ~1~.

Input

• Gồm một dòng chứa xâu ngoặc ~s~ ~(1 \le |s| \le 2 \times 10^5)~.
  
  
  

Output

• Nếu ~s~ là dãy ngoặc đúng, in ra ~1~ dòng gồm ~|s|~ số nguyên dương, số thứ ~i~ là số thứ tự của ngoặc tương ứng với ngoặc thứ ~i~.
• Nếu không, in ra ~-1~.
  
  

Sample Test 1

Input:

([])[]

Output:

4 3 2 1 6 5

Note:

• Số thứ tự của các cặp ngoặc là ~1-4, 2-3~ và ~5-6~.
  
  

Sample Test 2

Input:

([)]

Output:

-1

Note:

• Xâu ~s~ không phải là dãy ngoặc đúng.

Đây là phiên bản khó hơn của bài PA120. Điểm khác biệt duy nhất giữa hai bài là số ~k~ và giới hạn các số.

Sau khi bán hết sách, TDZ chuyển sang mở một quán cà phê.

Qua thăm dò, TDZ đã biết trước ngày khai trương sẽ có ~n~ khách, khách thứ ~i~ sẽ vào thời điểm ~h_i~. Để phục vụ lượng khách đến dồn dập, quán cà phê có thuê thêm một số nhân viên ưu tú. Mỗi nhân viên có thể hoạt động không ngừng nghỉ, mỗi lần chỉ phục vụ một khách trong đúng ~k~ đơn vị thời gian. Nhưng nếu một vị khách tới mà không nhận được sự phục vụ ngay thì sẽ lập tức bỏ đi.

Cụ thể, một vị khách đến ở thời điểm ~x~ nào đó, thì nhân viên sẽ phục vụ xong cho vị khách đó ở thời điểm ~x + k~. Khách đó sẽ rời quán và nhân viên tiếp tục phục vụ luôn khách tiếp theo (nếu có).

Hãy giúp TDZ tìm ra số lượng nhân viên cần thuê ít nhất mà vẫn đảm bảo tất cả các khách đều được phục vụ.

Input

• Dòng đầu tiên chứa 2 số nguyên dương ~n~, ~k~ (~n \leq 10^6, k \leq 10^9~).
• Dòng tiếp theo chứa ~n~ số nguyên dương ~h_1, h_2, h_3, \ldots, h_n~ tương ứng với thời điểm khách đến (~h_i \leq 10^9~).

Output

In ra số lượng nhân viên ít nhất cần thuê.

Subtasks

• Subtask ~1~ (~25\%~): ~n \leq 10^3~.
• Subtask ~2~ (~37.5\%~): ~n \leq 10^6, h_i \leq 10^6~.
• Subtask ~3~ (~37.5\%~): Không có điều kiện gì thêm.

Sample Test

Input:

5 2
1 2 5 3 5

Output:

2

Note: Thuê hai nhân viên:

• Nhân viên thứ nhất sẽ phục vụ khách thứ nhất, rồi đến khách thứ tư và cuối cùng phục vụ khách thứ ba.
• Nhân viên thứ hai phục vụ khách thứ hai rồi đến khách thứ năm.

Trên quốc lộ ~1A~ có ~N + 1~ trạm xăng từ đầu đến cuối con đường, đánh số từ ~0~ đến ~N~. Biết trạm xăng số ~i~ cách trạm xăng số ~i - 1~ một khoảng ~a_i~ km và trạm xăng số ~i~ bán ~1~ lít xăng với giá ~p_i~ đồng. Để đi được ~1~ km ta cần tiêu tốn ~1~ lít xăng.

TDZ đang bắt đầu đi trên quốc lộ ~1A~ thì hết xăng nên phải dừng tại trạm xăng số ~0~. Tính số tiền mua xăng nhỏ nhất mà TDZ phải mua để đến được trạm xăng số ~N~.

Input

• Dòng đầu tiên chứa số nguyên dương ~N~ (~N \leq 10^5~).
• Dòng thứ hai chứa ~N~ số nguyên dương ~a_1, a_2, \ldots, a_N~ (~a_i \leq 10^9~).
• Dòng thứ ba chứa ~N~ số nguyên dương ~p_0, p_1, \ldots, p_{N - 1}~ (~p_i \leq 10^9~).

Output

• In ra tổng số tiền nhỏ nhất dùng mua xăng để TDZ đến được trạm xăng số ~N~.

Sample Test

Input:

3
1 2 4
3 1 2

Output:

9

Note:

• TDZ mua ~1~ lít xăng ở trạm xăng thứ ~0~ (giá ~3~ đồng) để đi đến trạm xăng số ~1~.
• TDZ mua ~6~ lít xăng ở trạm xăng thứ ~1~ (giá ~6~ đồng) để đi đến trạm xăng cuối cùng.

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

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