Cho một tự nhiên ~n~ là cạnh của hình vuông. Hãy tính đường chéo của hình vuông đó.

Input

Gồm một số nguyên dương ~n~ (~n \leq 1000~).

Output

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

Sample Test

Input:

5

Output:

7.0710678

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

Cho số nguyên dương ~n~. Tính ~S = (1 + a^1 + a^2 + a^3 + \ldots + a^n) \ mod \ (10^9 + 7)~.

Input

• Gồm hai số nguyên dương ~a, n~ (~a, n \leq 10^9~).

Output

• In ra kết quả của ~S~.

Subtasks

• Subtask 1 (~50\%~): ~n \leq 10^6~.
• Subtask 2 (~50\%~): ~n \leq 10^9~.

Sample Tests

Bạn được cho một mảng gồm ~n~ số nguyên. Nhiệm vụ của bạn là: với mỗi đoạn con gồm ~k~ phần tử liêp tiếp, từ trái sang phải, tính tổng chi phí tối thiểu để tất cả các phần tử bằng nhau.

Bạn có thể tăng hoặc giảm từng phần tử với chi phí ~x~, trong đó ~x~ là chênh lệch giữa giá trị mới và giá trị ban đầu. Tổng chi phí của đoạn con là tổng của các chi phí tăng hoặc giảm mỗi phần tử trong đó.

Input

• Dòng đầu vào đầu tiên chứa hai số nguyên ~n~ và ~k~: số lượng phần tử của mảng và kích thước của đoạn con.
• Dòng tiếp theo chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~ - nội dung của mảng.

Output

• In ra ~n - k + 1~ số: các chi phí.

Constraints

• ~1 \leq k \leq n \leq 2 \times 10^5~
• ~1 \leq a_i \leq 10^9~.

Sample Test

Input:

8 3
2 4 3 5 8 1 2 1

Output:

2 2 5 7 7 1

Nhiệm vụ của bạn là với mỗi số ~k = 1, 2, \ldots, n~, đếm xem có bao nhiêu cách đặt ~2~ quân mã trên bàn cờ ~k \times k~ mà chúng không tấn công nhau.

Input

• Gồm một số nguyên dương ~n~ duy nhất (~2 \leq n \leq 10^4~).

Output

• In ra kết quả trên các dòng khác nhau.

Sample Test

Input:

8

Output:

0
6
28
96
252
550
1056
1848

Dãy ngoặc là một dãy chỉ gồm các kí tự mở ngoặc ( và đóng ngoặc ). Dãy ngoặc đúng là một dãy ngoặc được xây dựng dựa trên quy tắc sau:

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

Ví dụ, (()), ()() và ()(()) là các dãy ngoặc đúng; còn )( hay (() thì không.

Bạn được cho một xâu kí tự ~s~ là một dãy ngoặc đúng cùng dãy ~q~ số ~p_1,p_2,...,p_q~. Bạn cần thực hiện ~q~ lượt thao tác. Tại thao tác thứ ~i~, bạn cần làm những việc sau:

• Thay đổi kí tự thứ ~p_i~ của ~s~ (từ ( sang ) hoặc ngược lại) thì xâu kí tự ~s~ trở thành dãy ngoặc đúng.
• In ra vị trí ~a_i~ vừa tìm được và thay đổi kí tự ở vị trí này.

Chú ý rằng, ở bất kì thao tác nào, bạn bắt đầu khi xâu ~s~ đang là dãy ngoặc đúng. Do đó, việc thay đổi kí tự thứ ~p_i~ khiến ~s~ bây giờ chắc chắn không phải dãy ngoặc đúng, và ta dễ dàng chứng minh được vị trí ~a_i~ cần tìm ở trên là luôn tồn tại. Khi thay đổi kí tự ở vị trí ~a_i~, ~s~ trở lại là dãy ngoặc đúng.

Input: Nhập từ file "DAYNGOAC.INP"

• Dòng đầu tiên chứa hai số nguyên dương ~n,q~ ~(1 \le n \le 10^6, 1 \le q \le 6 \times 10^5)~, lần lượt là độ dài của dãy ngoặc và số thao tác bạn cần thực hiện.
• Dòng thứ hai chứa xâu kí tự ~s~ là một dãy ngoặc đúng độ dài ~n~ .
• Dòng thứ ba chứa ~q~ số nguyên ~p_1,p_2,...,p_n~ ~(1 \le p_q \le n)~ mô tả các thao tác cần thực hiện.

Output: Xuất ra file "DAYNGOAC.OUT"

In ra ~q~ số nguyên ~a_1,a_2,...,a_n~ là các vị trí tìm được ở các thao tác. Các số cần được viết trên một dòng, ngăn cách với nhau bởi dấu cách.

Subtask

• Subtask ~1~ (~20\%~ số test): ~n \le 500, q \le 300~.
• Subtask ~2~ (~30\%~ số test): ~n \le 7000, q \le 4200~.
• Subtask ~3~ (~25\%~ số test): ~n \le 2 \times 10^5, q \le 10^5~.
• Subtask ~4~ (~25\%~ số test): ~n \le 10^6, q \le 6\times10^5~.

Ví dụ

Sample Input 1

6 3
((()))
4 3 1

Sample Output 1

2 2 1

Giải thích

Trong ví dụ trên, ban đầu dãy ngoặc ~s~ là ((())). Các thao tác diễn ra như sau:

• Thao tác đầu tiên: Sau khi thay đổi kí tự ở vị trí ~p_1 = 4~, ~s~ trở thành (((()), để ~s~ trở lại là dãy ngoặc đúng, bạn cần thay đổi kí tự ở vị trí ~a_1 = 2~. Khi đó ~s~ trở thành ()(()).
• Thao tác tiếp theo: Sau khi thay đổi kí tự ở vị trí ~p_2 = 3~, ~s~ trở thành ())()), để ~s~ trở lại là dãy ngoặc đúng, bạn cần thay đổi kí tự ở vị trí ~a_2 = 2~. Khi đó ~s~ trở thành (()()).
• Thao tác cuối cùng: Sau khi thay đổi kí tự ở vị trí ~p_3 = 1~, ~s~ trở thành )()()), để ~s~ trở lại là dãy ngoặc đúng, bạn cần thay đổi kí tự ở vị trí ~a_3 = 1~. Khi đó ~s~ trở thành (()()).