Cho một xâu ~S~ chỉ gồm các ký tự (, ), {, }, [ và ]. Xâu ~S~ được gọi là hợp lệ nếu các ngoặc mở phải được đóng bởi cùng loại ngoặc và đúng thứ tự. Mọi ký tự mở phải có ký tự đóng tương ứng.

Hãy lập trình kiểm tra xem xâu ~S~ có phải là một dãy ngoặc hợp lệ hay không.

Ví dụ: Với ~S~ = {[()]} thì đây là dãy ngoặc hợp lệ vì các ngoặc được đóng mở đúng thứ tự. Còn với ~S~ = [(]), dãy không hợp lệ vì ngoặc vuông [ chưa được đóng trước khi ngoặc tròn ) xuất hiện.

Dữ liệu

Gồm một dòng duy nhất chứa xâu ~S~ (~1 \leq |S| \leq 10^5~).

Kết quả

In ra YES nếu xâu ~S~ là dãy ngoặc hợp lệ, ngược lại in ra NO.

Ví dụ

Input 1

{[()]}

Output 1

YES

Input 2

[(])

Output 2

NO

Cho một biểu thức hậu tố (Reverse Polish Notation - RPN) bao gồm các số nguyên và các toán tử +, -, *, /. Các phần tử (số hoặc toán tử) được phân cách nhau bởi một khoảng trắng.

Hãy tính và in ra giá trị của biểu thức đó.

Lưu ý:

• Phép chia / là phép chia nguyên (cắt bỏ phần thập phân, ví dụ ~14 / 3 = 4~, ~-14 / 3 = -4~).
• Dữ liệu đảm bảo biểu thức luôn hợp lệ và không có phép chia cho ~0~.
• Quá trình tính toán trung gian và kết quả cuối cùng luôn nằm trong giới hạn của kiểu số nguyên có dấu 64-bit.

Dữ liệu

Gồm một dòng duy nhất chứa chuỗi biểu thức hậu tố. Tổng độ dài của chuỗi không vượt quá ~10^5~ ký tự.

Kết quả

In ra một số nguyên duy nhất là kết quả của biểu thức.

Ví dụ

Input 1

2 3 1 * + 9 -

Output 1

-4

Input 2

10 6 9 3 + -11 * / * 17 + 5 +

Output 2

22

Cho một mảng ~A~ gồm ~N~ số nguyên. Với mỗi phần tử ~A[i]~ (~1 \le i \le N~), hãy tìm phần tử ~A[j]~ đầu tiên nằm bên phải (~j > i~) sao cho ~A[j] > A[i]~.

Nếu không tồn tại phần tử nào thỏa mãn, kết quả cho vị trí đó là -1.

Dữ liệu

• Dòng đầu tiên chứa số nguyên dương ~N~ (~1 \le N \le 10^5~).
• Dòng thứ hai chứa ~N~ số nguyên ~A[1], A[2], ..., A[N]~ (~|A[i]| \le 10^9~). Các số được phân cách nhau bởi khoảng trắng.

Kết quả

In ra một dòng gồm ~N~ số nguyên, cách nhau bởi khoảng trắng. Số thứ ~i~ là phần tử lớn hơn tiếp theo của ~A[i]~ (hoặc -1 nếu không có).

Ví dụ

Input 1

4
4 5 2 25

Output 1

5 25 25 -1

Giải thích 1

• Bên phải số 4, số lớn hơn đầu tiên là 5.
• Bên phải số 5, số lớn hơn đầu tiên là 25.
• Bên phải số 2, số lớn hơn đầu tiên là 25.
• Bên phải số 25 không còn phần tử nào lớn hơn nó, kết quả là -1.

Input 2

5
9 8 7 6 5

Output 2

-1 -1 -1 -1 -1

Cho một biểu đồ (histogram) gồm ~N~ cột liền kề nhau, cột thứ ~i~ có chiều rộng bằng ~1~ và chiều cao tương ứng là ~H[i]~.

Hãy tìm diện tích của hình chữ nhật lớn nhất có thể nằm trọn trong biểu đồ này. Các cạnh của hình chữ nhật phải song song với các trục tọa độ.

Dữ liệu

• Dòng đầu tiên chứa số nguyên dương ~N~ (~1 \le N \le 10^5~).
• Dòng thứ hai chứa ~N~ số nguyên không âm ~H[1], H[2], ..., H[N]~ (~0 \le H[i] \le 10^9~). Các số được phân cách nhau bởi khoảng trắng.

Kết quả

In ra một số nguyên duy nhất là diện tích của hình chữ nhật lớn nhất tìm được.

(Lưu ý: Kết quả có thể vượt quá giới hạn của số nguyên 32-bit, hãy sử dụng kiểu dữ liệu số nguyên 64-bit như long long trong C++).

Ví dụ

Input

6
2 1 5 6 2 3

Output

10

Giải thích

Hình chữ nhật lớn nhất được tạo bởi 2 cột có chiều cao 5 và 6. Chiều cao của hình chữ nhật bị giới hạn bởi cột thấp hơn là 5. Chiều rộng của hình chữ nhật là 2. Diện tích lớn nhất = ~5 \times 2 = 10~.

Cho một số nguyên dương vô cùng lớn được biểu diễn dưới dạng chuỗi ~S~. Hãy xóa đúng ~K~ chữ số khỏi chuỗi ~S~ sao cho số tạo thành từ các chữ số còn lại (vẫn giữ nguyên thứ tự) là nhỏ nhất có thể.

Lưu ý:

• Kết quả không được chứa các chữ số 0 vô nghĩa ở đầu (leading zeros).
• Nếu sau khi xóa, chuỗi kết quả trở thành rỗng, hãy in ra 0.

Dữ liệu

Gồm một dòng duy nhất chứa chuỗi ~S~ (~1 \le |S| \le 10^5~) và số nguyên dương ~K~ (~1 \le K < |S|~), cách nhau bởi một khoảng trắng.

Kết quả

In ra một chuỗi là số nhỏ nhất sau khi xóa đúng ~K~ chữ số.

Ví dụ

Input 1

1432219 3

Output 1

1219

Giải thích 1

Xóa các chữ số 4, 3, và 2 (số 2 đầu tiên) để tạo thành số 1219 là số nhỏ nhất.

Input 2

10200 1

Output 2

200

Giải thích 2

Xóa chữ số 1 ở đầu, chuỗi trở thành 0200. Bỏ đi số 0 vô nghĩa ở đầu ta được kết quả là 200.

Có ~N~ người đang xếp hàng mua vé tại siêu thị. Người thứ ~i~ (chỉ số bắt đầu từ ~0~ đến ~N-1~) muốn mua ~A[i]~ vé.

Mỗi giây, người đứng ở đầu hàng sẽ mua đúng 1 vé.

• Nếu họ vẫn cần mua thêm vé, họ sẽ quay vòng xuống đứng ở cuối hàng.
• Nếu họ đã mua đủ số vé mong muốn, họ sẽ rời khỏi hàng.

Hỏi sau bao nhiêu giây thì người ban đầu đứng ở vị trí thứ ~K~ (chỉ số ~0~) mua xong toàn bộ số vé của mình?

Dữ liệu

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~K~ (~1 \le N \le 10^5~, ~0 \le K < N~).
• Dòng thứ hai chứa ~N~ số nguyên ~A[0], A[1], ..., A[N-1]~ (~1 \le A[i] \le 10^9~).

Kết quả

In ra một số nguyên duy nhất là tổng số giây cần thiết để người thứ ~K~ mua xong vé. (Lưu ý: Kết quả có thể rất lớn, hãy sử dụng kiểu số nguyên 64-bit).

Ví dụ

Input 1

3 2
2 3 2

Output 1

6

Giải thích 1

• Giây 1: Người 0 mua 1 vé. Hàng đợi: [3, 2, 1]
• Giây 2: Người 1 mua 1 vé. Hàng đợi: [2, 1, 2]
• Giây 3: Người 2 (K) mua 1 vé. Hàng đợi: [1, 2, 1]
• Giây 4: Người 0 mua 1 vé và rời hàng. Hàng đợi: [2, 1]
• Giây 5: Người 1 mua 1 vé. Hàng đợi: [1, 1]
• Giây 6: Người 2 (K) mua 1 vé cuối cùng và rời hàng. Quá trình kết thúc tại giây thứ 6.

Input 2

4 0
5 1 1 1

Output 2

8

Cho một số nguyên dương ~N~. Hãy sinh ra ~N~ số nhị phân đầu tiên (bắt đầu từ số 1).

Gợi ý: Hãy sử dụng cấu trúc dữ liệu Hàng đợi (Queue) để sinh các số nhị phân tiếp theo bằng cách nối thêm 0 và 1 vào sau các số nhị phân đã sinh ra trước đó.

Dữ liệu

Gồm một dòng duy nhất chứa số nguyên dương ~N~ (~1 \le N \le 10^4~).

Kết quả

In ra một dòng duy nhất chứa ~N~ số nhị phân đầu tiên. Các số được phân cách nhau bởi một khoảng trắng.

Ví dụ

Input 1

5

Output 1

1 10 11 100 101

Input 2

10

Output 2

1 10 11 100 101 110 111 1000 1001 1010

Cho một bàn cờ vua kích thước ~8 \times 8~. Các cột được đánh số từ a đến h (từ trái qua phải) và các hàng được đánh số từ 1 đến 8 (từ dưới lên trên).

Một Quân Mã đang đứng ở tọa độ xuất phát, nó cần di chuyển đến tọa độ đích. Quân Mã di chuyển theo quy tắc chữ L của luật cờ vua (tiến 2 ô theo một hướng và 1 ô theo hướng vuông góc).

Hãy lập trình tìm số bước đi ít nhất để Quân Mã có thể đi từ ô xuất phát đến ô đích.

Dữ liệu

Gồm một dòng duy nhất chứa hai chuỗi tọa độ là vị trí xuất phát và vị trí đích, cách nhau bởi một khoảng trắng. Mỗi chuỗi tọa độ gồm 2 ký tự (1 chữ cái từ a đến h và 1 chữ số từ 1 đến 8).

Kết quả

In ra một số nguyên duy nhất là số bước đi tối thiểu. (Nếu xuất phát trùng với đích, in ra 0).

Ví dụ

Input 1

a1 b3

Output 1

1

Input 2

a1 h8

Output 2

6

Cho một mê cung được biểu diễn dưới dạng lưới kích thước ~N \times M~ (gồm ~N~ hàng và ~M~ cột). Các hàng được đánh số từ ~1~ đến ~N~ (từ trên xuống dưới), các cột được đánh số từ ~1~ đến ~M~ (từ trái qua phải).

Tại mỗi ô, ký tự . thể hiện đường có thể đi qua, và ký tự # thể hiện bức tường không thể đi xuyên qua. Từ một ô, bạn chỉ có thể di chuyển sang 4 ô kề cạnh (trên, dưới, trái, phải).

Hãy tìm số bước di chuyển ít nhất để đi từ ô xuất phát ~(x_1, y_1)~ đến ô đích ~(x_2, y_2)~.

Dữ liệu

• Dòng đầu tiên chứa hai số nguyên dương ~N, M~ (~1 \le N, M \le 1000~).
• Dòng thứ hai chứa 4 số nguyên ~x_1, y_1, x_2, y_2~ cho biết tọa độ hàng và cột của ô xuất phát và ô đích.
• ~N~ dòng tiếp theo, mỗi dòng chứa ~M~ ký tự (chỉ gồm . hoặc #) mô tả mê cung. (Dữ liệu đảm bảo ô xuất phát và ô đích luôn luôn là đường đi .).

Kết quả

In ra một số nguyên duy nhất là số bước di chuyển tối thiểu. Nếu không có đường đi tới đích, in ra -1.

Ví dụ

Input

3 3
1 1 3 3
.#.
..#
...

Output

4

Cho một mảng ~A~ gồm ~N~ số nguyên và một số nguyên dương ~K~. Một "cửa sổ" có kích thước ~K~ trượt từ trái sang phải qua mảng ~A~. Mỗi lần cửa sổ dịch chuyển sang phải 1 vị trí. Tại bất kỳ thời điểm nào, bạn chỉ có thể nhìn thấy đúng ~K~ phần tử nằm trong cửa sổ.

Hãy tìm và in ra giá trị lớn nhất trong cửa sổ tại mỗi bước trượt.

Dữ liệu

• Dòng đầu tiên chứa hai số nguyên dương ~N~ và ~K~ (~1 \le K \le N \le 10^5~).
• Dòng thứ hai chứa ~N~ số nguyên ~A[1], A[2], ..., A[N]~ (~-10^9 \le A[i] \le 10^9~), phân cách nhau bởi khoảng trắng.

Kết quả

In ra một dòng duy nhất chứa ~N - K + 1~ số nguyên. Số thứ ~i~ là giá trị lớn nhất của mảng trong khung cửa sổ bắt đầu từ vị trí ~i~ đến vị trí ~i + K - 1~.

Ví dụ

Input

8 3
1 3 -1 -3 5 3 6 7

Output

3 3 5 5 6 7

Giải thích

Các cửa sổ trượt lần lượt như sau:

• [1 3 -1] -3 5 3 6 7 => Max là 3
• 1 [3 -1 -3] 5 3 6 7 => Max là 3
• 1 3 [-1 -3 5] 3 6 7 => Max là 5
• 1 3 -1 [-3 5 3] 6 7 => Max là 5
• 1 3 -1 -3 [5 3 6] 7 => Max là 6
• 1 3 -1 -3 5 [3 6 7] => Max là 7