Sau ngày tháng ôn thi học kỳ căng thẳng, Egg tự thưởng cho mình rất nhiều sách. Ban đầu, Egg có ~N~ quyển sách xếp thành một chồng thẳng đứng, các quyển sách đã được sắp xếp ngăn nắp theo thứ tự: quyển sách trên cùng được đánh số là ~1~, quyền tiếp theo được đánh số là ~2~, ~\dots~ quyển sách dưới cùng được đánh số là ~N~ . Là một người khá lười nên mỗi khi để lại sách vào chồng sách, Egg không để sách vào chỗ cũ mà quăng luôn vào trên cùng.

Yêu cầu: Hãy xác định thứ tự cuối cùng của các quyển sách trong chồng sách.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~N~ ~(1 \leq N \leq 10^5)~ và ~q~ ~(1 \leq q \leq 10^5)~, là tổng số sách và số lần Egg đi lấy sách đọc.
• ~q~ dòng tiếp theo, mỗi dòng chứa một số nguyên ~x~ ~(1 \leq x \leq n)~ là mã số sách cần lấy.

Output

• ~N~ dòng, mỗi dòng là một số nguyên tương ứng với thứ tự cuối cùng của chồng sách.

Subtask

• Có ~30\%~ số test là ~q \leq 100~
• ~70\%~ số test còn lại là không giới hạn gì thêm.

Sample Input

3 4
1
3
2
1

Sample Output

1
2
3

Note

Chồng sách ban đầu được đánh số là: ~1~, ~2~, ~3~. Với các lần Egg đi lấy sách thì chồng sách thay đổi như sau:

• Sau khi lấy quyển sách được đánh số thứ ~1~ và đặt lại vào chồng sách: ~1~, ~2~, ~3~
• Sau khi lấy quyển sách được đánh số thứ ~3~ và đặt lại vào chồng sách: ~3~, ~1~, ~2~
• Sau khi lấy quyển sách được đánh số thứ ~2~ và đặt lại vào chồng sách: ~2~, ~3~, ~1~
• Sau khi lấy quyển sách được đánh số thứ ~1~ và đặt lại vào chồng sách: ~1~, ~2~, ~3~

Sau ~4~ lần đi lấy sách, chồng sách có thứ tự là ~1~, ~2~, ~3~

Cho ~2~ số nguyên ~N~ và ~K~. Hãy đếm số bộ ba ~(a, b, c)~ thỏa mãn các điều kiện sau:

• ~a, b, c~ là các số nguyên;
• ~1\leq a, b, c \leq N~;
• ~(a + b)~ ~\vdots~ ~K~;
• ~(b + c)~ ~\vdots~ ~K~;
• ~(c + a)~ ~\vdots~ ~K~.

Input

• Một dòng duy nhất chứa ~2~ số nguyên ~N~ và ~K~ ~(1\leq N, K \leq 2\times 10^5)~

Output

• Gồm một số nguyên là số lượng bộ ba ~(a,b,c)~ tìm được.

Subtask

• Có ~30\%~ số test là ~1 \leq n \leq 500~ và ~1 \leq k \leq 500~
• Các số test còn lại không yêu cầu gì thêm.

Sample Input

3 2

Sample Output

9

Note

Các bộ ba thỏa mãn yêu cầu đề bài là: ~(1, 1, 1), (2, 2, 2), (1, 1, 3),~ ~(1, 3, 1), (3, 1, 1), (1, 3, 3), ~ ~(3, 1, 3), (3, 3, 1), (3, 3, 3)~

Neko là một đại kỳ thủ trong trò chơi NEGIKO, với một biệt danh cực kì nổi tiếng là "Bố của các kỳ thủ NEGIKO". Anh ấy giỏi chơi trò này đến nỗi anh có thể nhìn thấy được có bao nhiêu cách để giành chiến thắng. Tuy nhiên, vì một ngày nọ anh ấy thức khuya leo rank thách đấu nên ngày hôm đó anh ấy không thể đếm được chính xác có bao nhiêu cách. Vì vậy nên bạn, với tư cách là bạn thân chí cốt của anh ấy, hãy tạo ra một chương trình giúp đếm số cách để Neko chiến thắng.

Biết trò chơi NEGIKO có luật chơi như sau:

Neko cầm ~n~ thẻ bài, mỗi thẻ bài có giá trị ~a_i~.

Đối thủ cầm ~m~ thẻ bài, mỗi thẻ bài có giá trị ~b_i~.

Mỗi ván chơi Neko sẽ chọn bất kì ~k~ thẻ bài của anh ấy và đối thủ sẽ chọn bất kì ~k~ thẻ bài của cậu ấy. Neko sẽ giành chiến thắng khi trong ~k~ thẻ bài từ Neko và ~k~ thẻ bài từ đối thủ được chọn:

• Thẻ bài có giá trị cao nhất của Neko lớn hơn thẻ bài có giá trị cao nhất của đối thủ
• Thẻ bài có giá trị cao thứ hai của Neko lớn hơn thẻ bài có giá trị cao thứ hai của đối thủ, ~\dots~
• Thẻ bài có giá trị cao thứ ~k~ của Neko lớn hơn thẻ bài có giá trị cao thứ ~k~ của đối thủ.

Yêu cầu: Hãy đếm số cách chọn để Neko giành chiến thắng.

Input:

• Dòng thứ nhất chứa số nguyên dương ~n~, ~m~, và ~k~ (~n \le 1000~, ~m \le 1000~, ~k \le 10~).
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1~, ~a_2~, …, ~a_n~ (~a_i \le 2 \times 10^5~, ~i~ = ~1~, ~2~, …, ~n~).
• Dòng thứ ba chứa ~m~ số nguyên dương ~b_1, b_2, … b_m~ (~b_i \le 2 \times 10^5~, ~i~ = ~1~, ~2~, …, ~m~).

Output:

• Số cách chia thỏa mãn yêu cầu đề bài, do đáp án có thể rất lớn nên in ra phần chia dư cho ~10^9 + 9~.

Subtask:

• ~10\%~ số test có ~n \le 10,m \le 10, k = 1~.
• ~10\%~ số test tiếp theo có ~n \le 100, m \le 100, k \le 2~.
• ~30\%~ số test tiếp theo có ~n \le 100, m \le 100~.
• Số test còn lại không có giới hạn gì thêm.

Sample Input:

3 2 2
3 4 3
2 3

Sample Output:

2

Note:

Có ~2~ cách chọn thỏa mãn:

• Neko chọn ~3~ (ở vị trí đầu) và ~4~, đối thủ chọn ~2~ và ~3~.
• Neko chọn ~3~ (ở vị trí cuối) và ~4~, đối thủ chọn ~2~ và ~3~.

Nhân dịp cuối năm được học sinh giỏi, illya được mẹ dẫn đi gian hàng hội chợ. Bước vào một quầy bắn cung, có ~n~ quả bóng bay được đính trên tường xếp thành một hàng ngang, mỗi quả bóng đều được dán lên một số điểm, lần lượt từ trái sang phải, quả bóng thứ nhất có số điểm là ~a_1~, quả bóng thứ hai có số điểm là ~a_2~, ~\dots~, quả bóng thứ ~n~ có số điểm là ~a_n~. Để làm khó người chơi, người chủ quầy quy định rằng các quả bóng mà illya bắn phải nằm liên tiếp nhau và quả bóng có số điểm ít nhất trong những quả bóng mà illya bắn phải có giá trị từ ~x~ đến ~y~. Để nhận được phần thưởng, illya phải bắn những quả bóng và giành được điểm số cao nhất có thể. Hãy giúp illya đạt được phần thưởng nhé!

Input

• Dòng đầu tiên chứa số nguyên ~n~ ~(1 \leq n \leq 10^6)~, là số quả bóng bay được dính trên tường.
• Dòng thứ hai chứa hai số nguyên ~x~ và ~y~ ~(-10^9 \leq x \leq y \leq 10^9)~.
• Dòng thứ ba chứa ~n~ số nguyên ~a_1~, ~a_2~, ~\dots~, ~a_n~ ~(-10^9 \leq a_i \leq 10^9)~.

Output

• Dòng đầu tiên chứa một số nguyên là số điểm lớn nhất thỏa mãn yêu cầu đề bài.
• Dòng thứ hai chứa hai số nguyên ~l~ và ~r~ ~(1 \leq l \leq r \leq n)~ là chỉ số của quả bóng thứ ~l~ và quả bóng thứ ~r~, mô tả danh sách các quả bóng có tổng điểm lớn nhất thỏa mãn yêu cầu đề bài. Dữ liệu vào đảm bảo có ít nhất một danh sách thỏa mãn. Nếu có nhiều danh sách các quả bóng cho ra điểm lớn nhất, bạn được in ra một phương án bất kì.

Subtask

• Có ~20\%~ số test là ~1 \leq n \leq 100~
• Có ~20\%~ số test là ~1 \leq n \leq 5000~
• Có ~30\%~ số test là ~1 \leq n \leq 2 \times 10^5~
• Có ~30\%~ số test là ~1 \leq n \leq 10^6~

Sample Input 1

7 
6 30
9 27 4 20 8 13 50

Sample Output 1

91
4 7

Sample Input 2

7
1 5
1 4 2 6 6 2 7

Sample Output 2

28
1 7

Ở một vương quốc độc tài nọ, vị vua anh minh Trí Fang từ lâu đã được biết đến với khả năng thao túng kẻ địch bằng những chiến thuật phòng thủ tài ba của mình.

Vào một ngày nọ, Trí quyết định rà soát khả năng phòng thủ của vương quốc của cậu ấy.

Vương quốc Trí Fang bao gồm ~n~ thành trì quan trọng được kết nối với nhau bởi ~n-1~ con đường hai chiều. Những con đường này đảm bảo rằng bất kỳ ~2~ thành trì nào cũng có thể đi đến được nhau.

Thành trì ~i~ có chỉ số chiến thuật là ~c_i~. Để vương quốc của cậu ấy an toàn, Trí phải đảm bảo rằng, với bất kì ~1~ thành trì nào bị chiếm đóng, trong ~n-1~ thành trị còn lại, những thành trì có thể đến được nhau phải có cùng chỉ số chiến thuật. Biết rằng nếu ~1~ thành trì bị chiếm đóng thì những con đường nối với thành trì đó sẽ không thể sử dụng được.

Trí muốn biết rằng với mỗi thành trì ~i~, nếu thành trì này bị chiếm đóng, ~n-1~ thành trì còn lại, những thành trì có thể đến được nhau có cùng một chỉ số chiến thuật hay không. Là một thần dân trung thành của Trí Fang, bạn hãy giúp vị vua kính mến của chúng ta tìm ra những thành trì ~i~ thỏa mãn.

Input

• Dòng đầu tiên chứa số nguyên ~n~ ~(1 \le n \le 10^{6})~.
• ~n-1~ dòng tiếp theo, mỗi dòng gồm ~2~ số nguyên ~u, v~ ~(1 \le u,v \le n)~ thể hiện có con đường hai chiều nối thành trì ~u~ và ~v~.
• Dòng cuối cùng chứa ~n~ số nguyên ~c_1, c_2, \dots, c_n~ ~(1 \le c_i \le 2\times 10^{6}, 1 \leq i \leq n)~.

Output

• Nếu không tồn tại thành trì ~i~ nào thỏa mãn nếu thành trì này bị chiếm đóng, ~n-1~ thành trì còn lại, những thành trì có thể đến được nhau phải có cùng một chỉ số chiến thuật, thì in ra NO trên một dòng duy nhất. Ngược lại, in ra YES ở dòng đầu tiên, dòng thứ hai in ra danh sách tăng dần các thành trì thỏa mãn.

Subtask

• Subtask ~1~ (~20\%~ số điểm): ~1 \le n \le 5000~.
• Subtask ~2~ (~20\%~ số điểm): Mỗi thành trì nối trực tiếp với tối đa ~2~ thành trì khác.
• Subtask ~3~ (~20\%~ số điểm): ~1 \le n \le 2\times 10^{5}~.
• Subtask ~4~ (~40\%~ số điểm): Không có ràng buộc gì thêm.

Sample Input 1

4
1 2
2 3
3 4
1 2 1 1

Sample Output 1

YES
2 

Sample Input 2

4
1 2
2 3
3 4
1 2 1 2

Sample Output 2

NO

Một dãy ~f~ có độ dài vô hạn được định nghĩa như sau:

• ~f_0 = 0~.
• ~f_1 = 1~.
• ~f_i = (f_{i - 1} + 2 \times f_{i - 2})~ mod ~1058375681~ ~\forall~ ~i > 1~ (~a~ mod ~b~ là phần dư khi lấy ~a~ chia ~b~).

Cho một dãy ~a~ có độ dài ~n~ ~(a_1, a_2, ... , a_n)~, ban đầu tất cả phần tử của dãy đều bằng ~0~, hãy thực hiện các truy vấn thuộc một trong hai loại sau:

• Sao chép một đoạn dãy ~f~ và dán vào dãy ~a~: cho ba số ~l~, ~r~ và ~k~, gán ~a_i = f_{i + k - 1}~ ~\forall~ ~l \leq i \leq r~.
• Tính tổng một đoạn dãy ~a~: cho hai số ~l, r~, tính ~(a_l + a_{l + 1} + ... + a_r)~ mod ~1058375681~.

Input

Dòng đầu tiên chứa ~2~ số nguyên dương ~n, q~ tương ứng là độ dài dãy ~a~ và số truy vấn cần xử lý ~(1 \leq n, q \leq 10^5)~.

~q~ dòng tiếp theo, mỗi dòng thể hiện một trong hai loại truy vấn sau:

• ~1~ ~l~ ~r~ ~k~: gán ~a_i = f_{i + k - 1}~ ~\forall~ ~l \leq i \leq r~.

• ~2~ ~l~ ~r~: tính ~(a_l + a_{l + 1} + ... + a_r)~ mod ~1058375681~.

Trong mọi truy vấn ~1 \leq l \leq r \leq n~, ~1 \leq k \leq 10^9~.

Output

Với mỗi truy vấn loại ~2~, in ra trên một dòng giá trị cần tìm.

Subtask

• ~15\%~ số test có ~n, q \leq 1000, k \leq 10^5~.
• ~25\%~ số test khác có ~n, q, k \leq 10^5~.
• Các test còn lại không có ràng buộc gì thêm.

Sample Input

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

Sample Output

5
599
258
85