Sau kỳ thi đánh giá năng lực đầy cam go và trầm cảm chị Hiền đã xuất sắc được nhận vào UET. Để ăn mừng cho kết quả đó hội bạn thân của chị đã quyết định tổ chức một bữa ăn nhậu ở quán ăn ABC nằm trên con đường nơi chị sống có số nhà là ~Y~.

Nhưng khổ nỗi sau khi hết ~F0~, do ảnh hưởng của di chứng nên chị Hiền đã gặp khó khăn khi xác định phương hướng. Chị tự sáng tạo ra cho mình cách đi kiểu mới.

Con đường nhà chị Hiền các nhà được đánh số lần lượt bằng các số tự nhiên liên tiếp. Ban đầu chị Hiền xuất phát ở nhà có số nhà là ~X (X~ luôn không đổi), ở lần đi tìm thứ ~i~, chị Hiền sẽ đi đến căn nhà có số nhà ~X + (-1)^i \times 2^{i-1}~.

Ví dụ: Lần ~1~ đi tìm chị sẽ đến căn nhà có số nhà ~X–1~, lần ~2~ đi tìm chị sẽ đến căn nhà có số nhà ~X + 2~, lần ~3~ đi tìm chị sẽ đến căn nhà có số nhà ~X – 4~, ….

Hãy in ra số lần chị Hiền cần phải đi theo cách trên và khoảng cách chị Hiền cần phải đi để đến được căn nhà có số nhà là ~Y~.

Input

• Gồm ~1~ dòng chứa ~2~ số nguyên ~X~ và ~Y~ cách nhau bởi ~1~ dấu cách. ~(0 \le |X|, |Y| \le 10^{10} )~

Output

• Ghi ra số lần đi tìm và khoảng cách chị Hiền phải đi từ ~X~ đến ~Y~.

Sample Input

3 6

Sample Output

4 17

Note

• Lần ~1~ đi từ ~3~ về ~2~, quãng đường đi được là ~1~
• Lần ~2~ đi từ ~2~ đến ~5~, quãng đường đi được là ~3~
• Lần ~3~ đi từ ~5~ về ~- 1~, quãng đường đi được là ~6~
• Lần ~4~ đi từ ~- 1~ đến ~11~ nhưng gặp căn nhà số ~6~ nằm trên quãng đường đó nên chỉ đi được ~7~

Tổng quãng đường là ~17~ sau ~4~ lần đi tìm.

Subtask

• ~50\%~ số test có ~0 \le |X|, |Y| \le 10^{6} ~
• ~50\%~ số test còn lại không có điều kiện gì thêm

Chó Vàng đang đi ngang qua một dãy hoa tuyệt đẹp, tức cảnh sinh tình, Chó Vàng lại nhớ đến crush đã nửa ngày không gặp.

Anh muốn hái một vài bông và gom lại thành một bó hoa to để tặng crush của mình. Dãy hoa gồm ~n~ bông hoa với nhiều màu sắc sặc sỡ mọc thành một hàng, Chó Vàng chỉ được phép hái một đoạn bất kỳ gồm ~k~ bông hoa liên tiếp nhau.

Vẻ đẹp của bó hoa sẽ được tính bằng số lượng màu sắc khác nhau của những bông hoa thuộc bó hoa đó. Chó Vàng muốn dành tặng cho crush những thứ tốt đẹp nhất nhưng chưa biết chọn thế nào để được bó hoa đẹp nhất. Bạn hãy giúp Chó vàng nhé!

Input

• Dòng đầu là hai số nguyên ~n~, ~k~ lần lượt là số lượng bông hoa trong dãy và số lượng hoa Chó Vàng được phép hái. ~(1 \le k \le n \le 3 \times 10^5)~

• Dòng thứ hai là dãy số nguyên dương ~a_1, a_2, .., a_n~ lần lượt là vẻ đẹp của ~n~ bông hoa. ~(1 \le a_i \le 10^9)~

Output

• Một số nguyên là vẻ đẹp của bó hoa đẹp nhất Chó Vàng có thể hái.

Sample Input

7 3
1 2 1 2 3 3 1

Sample Output

3

Note

• Dãy ~3~ bông hoa liên tiếp có số lượng màu khác nhau nhiều nhất là ~[1, 2, 3]~.

Subtask

• ~40\%~ số test có ~k \le n \le 100~

• ~40\%~ số test khác có ~k \le n \le 10^4~

• ~20\%~ số test còn lại không có điều kiện gì thêm

~Mike~ đi du lịch nước ~Pa~ và mua được một dãy ngoặc đúng rất đẹp.

Một dãy ngoặc đúng được định nghĩa như sau:

• Xâu rỗng là ~1~ dãy ngoặc đúng.
• Nếu ~A~ là ~1~ dãy ngoặc đúng thì ~(A)~ là ~1~ dãy ngoặc đúng.
• Nếu ~A~ và ~B~ là ~2~ dãy ngoặc đúng thì ~AB~ là ~1~ dãy ngoặc đúng.

~Mike~ dự định khi về nhà sẽ đem khoe với mọi người, tuy nhiên một quả tên lửa không biết của ai từ trên trời rơi đã xuống và làm bay mất một vài dấu ngoặc và chỉ còn lại đúng ~n~ dấu ngoặc trong dãy.

Dù không bị thương nhưng ~Mike~ vẫn rất buồn vì dãy ngoặc đã bị mất đi vẻ đẹp vốn có của nó, bạn hãy giúp ~Mike~ khôi phục lại vẻ đẹp ấy bằng cách chèn vào số lượng ít nhất các dấu ngoặc sau cho dãy ngoặc ấy vẫn trở thành một dãy ngoặc đúng nhé!!!

Lưu ý: Đề bài luôn đảm bảo tồn tại ít nhất một đáp án thỏa mã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~ kí tự miêu tả dãy ngoặc.

Output

In ra dãy ngoặc đúng với số lần chèn ít nhất. Nếu có nhiều dãy ngoặc thỏa mãn, in ra một dãy bất kì.

Sample Input 1

2
)(

Sample Output 1

()()

Sample Input 2

3
(()

Sample Output 2

(())

Subtask

• ~20\%~ số test có ~n \leq 100~

• ~20\%~ khác có ~n \leq 1000~

• ~60\%~ còn lại không có ràng buộc gì thêm

Dế Mèn mới được học về toán tử OR, anh đang muốn luyện tập bằng một bài liên quan tới toán tử OR trên trang web VNOJ. Nhưng bài toán này quá khó nên Dế Mèn muốn nhờ các bạn giúp :

Xét dãy ~a~ gồm ~n~ phần tử. Thực hiện ~q~ truy vấn sau trên dãy ~a~.

• ~u \ \ \, v~ : ~a_u = v~

Sau mỗi truy vấn, in ra độ dài của dãy con liên tiếp dài nhất của dãy ~a~ thỏa mãn biểu thức :

• ~a_l + a_{l+1} + ... + a_r = a_l \ | \ a_{l+1} \ | \ ... \ | \ a_r~. Trong đó "~|~" là toán tử OR.

Input

• Dòng đầu tiên nhập vào hai số nguyên dương ~n~ và ~q~ là độ dài của dãy ~a~ và số truy vấn cần trả lời ~(1 \le n,\ q \le 10^5)~.
• Dòng thứ hai nhập vào ~n~ số nguyên dương ~a_1, a_2, ..., a_n~. ~(1 \le a_i \le 10^9)~
• ~q~ dòng tiếp theo, mỗi dòng nhập hai số nguyên dương ~u~ và ~v~ tương ứng với truy vấn gán ~a_u = v~. ~(1 \le u \le n, 1 \le v \le 10^9)~

Output

• In ra ~q~ dòng, dòng thứ ~i~ trả lời câu hỏi sau truy vấn thứ ~i~.

Sample Input

5 4
1 2 3 4 5
1 3
1 1
3 8
4 6

Sample Output

2
2
4
3

Note

• Sau truy vấn ~2~, dãy con dài nhất thỏa điều kiện là dãy từ ~1~ đến ~2~.
• Sau truy vấn ~3~, dãy con dài nhất thỏa điều kiện là dãy từ ~1~ đến ~4~.

Subtask

• ~25\%~ số test có ~n,\ q \le 10^2~
• ~25\%~ số test tiếp theo có ~n,\ q \le 10^3~
• ~50\%~ số test còn lại không có điều kiện gì thêm

Bản đồ của ~1~ khu rừng được chia thành các ô vuông bằng nhau và biểu diễn dưới dạng mặt phẳng ~Oxy~ (mỗi ô ứng với ~1~ điểm có tọa độ nguyên). Một đám cháy rừng sẽ diễn ra như sau :

• Ban đầu chỉ có ~1~ ô bị cháy.
• Sau ~1~ đơn vị thời gian, đám cháy sẽ lan sang các ô có chung đỉnh hoặc chung cạnh với các ô đang cháy.

Cho ~2~ điểm ~A(0, a)~ và ~B(b, 0)~ trên mặt phẳng, bạn cần phải đi từ ~A~ đến ~B~ sao cho mỗi bước chỉ được đi xuống hoặc sang phải. Ngoài ra bạn cần trả lời các truy vấn sau:

• Mỗi truy vấn cho ~1~ cặp số ~x, t~. Hỏi nếu có ~1~ đám cháy ở ô ~(x, x)~ và đã kéo dài ~t~ đơn vị thời gian thì có bao nhiêu cách đi từ ~A~ tới ~B~ mà không đi qua các ô bị cháy ?

Ví dụ khi có điểm ~A(0, 4)~ và ~B(4, 0)~:

Input

• Gồm ~2~ dòng chứa ~2~ số nguyên ~a~ , ~b~ (thể hiện tọa độ điểm ~A~ và ~B~ như đề bài) và số nguyên ~Q~ là số lượng truy vấn. ~(1 \le a, b \le 10^{6})~ ~(1 \le q \le 3 \times 10^{5})~
• ~Q~ dòng tiếp theo , mỗi dòng chứa ~2~ số nguyên ~x~ , ~t~ là câu hỏi cho mỗi truy vấn. ~(0 \le |x|, t \le 10^{9})~

Output

• In ra ~Q~ dòng, mỗi dòng là phần dư của kết quả truy vấn đó sau khi chia cho ~10^9+7~.

Sample Input

4 4 2
2 1
2 0

Sample Output

2 
34

Subtask

• ~20\%~ số test có ~a \times b \le 1000000~ , ~q = 1~
• ~20\%~ số test tiếp theo có ~q = 1~ và ~x \le 0~
• ~60\%~ số test còn lại không có điều kiện gì thêm