FireGhost130104 là một người rất đam mê lập trình và đặc biệt thích truyền bá lan rộng lập trình thi đấu đến mọi người. Hôm nay FireGhost130104 thử thách các đệ tử của mình bằng một câu hỏi rất đơn giản: cho hai số ~L~ và ~R~, tổng ~\text{XOR}~ của đoạn ~[L, R]~ là bao nhiêu?.

Input

• Dòng đầu tiên chứa số nguyên dương ~T~ ~(1 \le T \le 10^{5})~ - số câu hỏi FireGhost130104 đưa ra.

• Dòng thứ ~i~ trong ~T~ dòng tiếp theo chứa hai số nguyên dương ~L, R~ (~1 \le L \le R < 2^{63})~ thể hiện một câu hỏi của FireGhost130104.

Output

• In ra ~T~ dòng lần lượt là đáp án của các câu hỏi theo thứ tự nhập vào.

Scoring

• Subtask ~1~ (~20~ điểm): ~1 \le l \le r \le 1000~.

• Subtask ~2~ (~30~ điểm): ~1 \le l \le r \le 10^{6}~.

• Subtask ~3~ (~50~ điểm): Không có điều kiện gì thêm.

Sample Input 1

1
4 8

Sample Output 1

8

Notes

• tổng ~\text{XOR}~ của đoạn ~[4 , 8]~ là ~4~ ~\oplus~ ~5~ ~\oplus~ ~6~ ~\oplus~ ~7~ ~\oplus~ ~8~ ~= 8~.

Nhân dịp DeMen100ns vừa được học về dãy số, thầy giáo ra một bài tập về nhà như sau:

Tìm một dãy số ~a~ gồm ~n~ phần tử ~a_1,\ a_2, \ldots,\ a_n~ thỏa mãn các điều kiện:

• Chỉ gồm các phần tử nguyên dương

• Là một dãy tăng (~a_i < a_{i + 1}~ với ~1 \leq i \lt n~)

• Không tồn tại tập giá trị ~i_1,\ i_2, \ldots,\ i_k~ và giá trị ~j~ (~1 \leq i_1 \lt i_2 \lt \ldots \lt i_k \lt j \leq n~) mà ~a_{i_1} + a_{i_2} + \ldots + a_{i_k} = a_j~

• ~a_n \leq n \times \sqrt{n}~

Dù đã thử viết ra nhiều dãy số nhưng nhưng DeMen100ns vẫn chưa thể nào tìm ra được một dãy số thỏa mãn các điều kiện trên. Hạn nộp bài tập đã gần đến, bạn hãy giúp DeMen100ns tìm ra một dãy số thỏa mãn nhé.

Input

Một dòng duy nhất chứa số nguyên dương ~n~ (~1 \leq n \leq 40~) là số phần tử của dãy ~a~.

Output

In ra dãy ~a~ thỏa điều kiện đề bài. Nếu có nhiều dãy ~a~ thỏa mãn thì chỉ cần in ra một dãy bất kỳ. Dữ liệu đảm bảo luôn tồn tại ít nhất một dãy ~a~ thỏa điều kiện.

Scoring

Bài có ~40~ test, mỗi test có ~n~ từ ~1~ đến ~40~, và có giá trị ~2.5\%~

Sample Input 1

1

Sample Output 1

1

Sample Input 2

2

Sample Output 2

1 2

Sample Input 3

3

Sample Output 3

1 3 5

Sample Input 4

4

Sample Output 4

1 2 4 8

kazamahoang đang chăm chú học thì bỗng nhận được thông báo: trường học đã bị xâm chiếm bởi virus lạ, người nhiễm virus này sẽ không thể có người yêu trong ~10~ năm tiếp theo.

Lớp học gồm ~n~ học sinh ngồi trên một đường thẳng. Virus này lây nhiễm theo một cách đặc biệt: từ cơ thể vật chủ, mỗi phút nó sẽ "tấn công" hệ miễn dịch của người bên cạnh, cho đến khi người đó nhiễm virus. Nói cách khác, học sinh thứ ~i + 1~ sẽ bị lây nhiễm virus từ học sinh thứ ~i~.

Hệ miễn dịch của mỗi học sinh có một sức mạnh riêng; học sinh thứ ~i~ có sức đề kháng là ~p_i~, điều này đồng nghĩa mỗi phút học sinh đó có ~p_i\%~ khả năng nhiễm virus.

Khi nhận được thông báo, virus đã xâm nhập trường học được ~t~ phút. kazamahoang rất lo lắng vì anh đã FA ~18~ năm, và tất nhiên không muốn con số đó trở thành ~28~. Anh ấy muốn biết giá trị kì vọng của số người bị nhiễm virus sau ~t~ phút, hãy giúp kazama nhé!

Input

Dòng đầu tiên gồm hai số nguyên dương ~n~ — số học sinh trong lớp và ~t~ — thời gian virus đã xâm nhập trường học (~1 \le n, t \le 2000~).

Dòng tiếp theo gồm ~n~ số nguyên dương ~p_1, p_2, \ldots, p_n~ (~1 \le p_i \le 100~) — sức đề kháng của mỗi học sinh.

Output

Giá trị kì vọng của số người nhiễm virus sau ~t~ phút. Đáp án của bạn sẽ được chấp nhận nếu sai số không vượt quá ~10^{-9}~. Nói cách khác, gọi đáp án của bạn là ~a~, đáp án của jury là ~b~, đáp án của bạn sẽ được chấp nhận nếu ~\frac{|a - b|}{max(1,\ |b|)} \le 10^{-9}~.

Scoring

• Subtask ~1~ (~20~ điểm): ~n, t \le 20~.

• Subtask ~2~ (~80~ điểm): không có ràng buộc gì thêm.

Sample Input 1

2 3
50 100

Sample Output 1

1.625000000

Notes

Ta sẽ liệt kê tất cả các trường hợp có thể xảy ra:

• Học sinh ~1~ không bị nhiễm virus sau ~3~ phút. Xác suất xảy ra trường hợp này là ~\frac{1}{2} \cdot \frac{1}{2} \cdot \frac{1}{2} = \frac{1}{8}~.

• Học sinh ~1~ bị nhiễm virus ở phút thứ ~3~. Xác suất xảy ra trường hợp này là ~\frac{1}{2} \cdot \frac{1}{2} \cdot \frac{1}{2} = \frac{1}{8}~.

• Học sinh ~1~ bị nhiễm virus ở phút thứ ~2~, kéo theo học sinh ~2~ bị nhiễm virus ở phút thứ ~3~. Xác suất xảy ra trường hợp này là ~\frac{1}{2} \cdot \frac{1}{2} \cdot 1 = \frac{1}{4}~.

• Học sinh ~1~ bị nhiễm virus ở phút thứ ~1~, kéo theo học sinh ~2~ bị nhiễm virus ở phút thứ ~2~. Xác suất xảy ra trường hợp này là ~\frac{1}{2} \cdot 1 = \frac{1}{2}~.

Vì vậy, giá trị kì vọng của số học sinh bị nhiễm virus sau ~3~ phút là ~0 \cdot \frac{1}{8} + 1 \cdot \frac{1}{8} + 2 \cdot \frac{1}{4} + 2 \cdot \frac{1}{2} = \frac{13}{8}~.

Hau có dãy ngoặc độ dài ~n~ và ~q~ truy vấn dạng ~(l, r)~. Với mỗi truy vấn, hãy giúp Hau tìm hai chỉ số ~L, R~ thỏa mãn:

• Dãy con tạo bởi đoạn ~[L, R]~ tạo thành dãy ngoặc đúng

• ~L \le l~ và ~r \le R~

• ~R - L~ nhỏ nhất có thể

Input

Dòng đầu tiên chứa ~2~ số nguyên dương ~n, q~ (~n, q \leq 2 \cdot 10^5~) — độ dài dãy ngoặc và số truy vấn của bài toán.

Dòng thứ hai chứa dãy ngoặc độ dài ~n~. ~q~ dòng tiếp theo, dòng thứ ~i~ gồm ~2~ số ~l, r~ (~1 \leq l \leq r \leq n~) thể hiện truy vấn thứ ~i~.

Output

Gồm ~q~ dòng. Dòng thứ ~i~ trả lời cho truy vấn thứ ~i~ chứa ~2~ chỉ số ~L, R~ biểu diễn dãy tìm được nếu tồn tại đáp án, ngược lại in ~-1~.

Scoring

• Subtask ~1~ (~50~ điểm): ~0 < n \le 1000~.

• Subtask ~2~ (~50~ điểm): không có ràng buộc gì thêm.

Sample Input 1

10 10
))(()()()(
3 7
4 4
6 9
5 7
1 6
1 7
3 8
5 8
7 9
7 10

Sample Output 1

-1
4 5
6 9
4 7
-1
-1
-1
4 9
6 9
-1

Xét một tập ~S~ gồm ~k~ phần tử, kí hiệu là ~S_k=\{s_1,s_2,\dots,s_k\}~, định nghĩa ~f(S_k)=s_1\cdot s_2 \cdot \ldots \cdot s_k~ là giá trị của tập ~S_k~.

Cho một dãy số gồm ~n~ số nguyên dương ~a_1,a_2,...,a_n~. Với một đoạn ~a[l..r]~, gọi ~g(l,r)=\sum_{S_k \subset \{a_l,a_{l+1},\ldots,a_r\}}f(S_k)~ là giá trị của đoạn con này. Ta sẽ lần lượt thực hiện ~q~ truy vấn trên dãy số đã cho:

• 1 l r: Tính ~g(l, r)~ - tổng giá trị của các tập con thuộc tập hợp ~\{a_l, a_{l + 1}, \ldots, a_r\}~.

• 2 i x: Thay đổi ~a_i = x~.

Yêu cầu: Với mỗi truy vấn loại 1, hãy in ra ~g(l, r)~ trong truy vấn tương ứng.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n, k~ (~1 \le n \le 10^5, 1 \le k \le 20~).

• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ (~1 \le a_i \le 10^9~).

• Dòng thứ ba chứa số nguyên dương ~q~ (~1 \le q \le 10^5~).

• ~q~ dòng tiếp theo, mỗi dòng mô tả một truy vấn thuộc một trong hai dạng nêu trên.

• Trong các truy vấn loại ~1~, ~1\le l\le r\le n~; trong các truy vấn loại 2, ~1\le i \le n~ và ~1\le x \le 10^9~.

Output

• In ra nhiều dòng, mỗi dòng là đáp án cho truy vấn loại ~1~ tương ứng trong dữ liệu đầu vào. Vì đáp án có thể rất lớn, hãy in ra số dư khi chia cho ~10^9 + 7~.

Scoring

• Subtask ~1~ (~20~ điểm): ~n, q \le 1000~

• Subtask ~2~ (~30~ điểm): ~a_i, x \le 2~

• Subtask ~3~ (~50~ điểm): không có ràng buộc gì thêm.

Sample Input 1

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

Sample Output 1

149
74

Notes

Ở test ví dụ trên:

• Ở truy vấn thứ ~1~, ta được yêu cầu tính ~g(1, 4)~. Đáp án của truy vấn này là ~3 \cdot 10 + 3 \cdot 3 + 3 \cdot 5 + 10 \cdot 3 + 10 \cdot 5 + 3 \cdot 5 = 149~.

• Ở truy vấn thứ ~2~, ta thực hiện thay đổi ~a_3 = 4~. Lúc này, ~a = [3, 10, 4, 5, 10]~.

• Ở truy vấn thứ ~3~, ta thực hiện thay đổi ~a_2 = 6~. Lúc này, ~a = [3, 6, 4, 5, 10]~.

• Ở truy vấn thứ ~4~, ta được yêu cầu tính ~g(2, 4)~. Đáp án của truy vấn này là ~6 \cdot 4 + 6 \cdot 5 + 4 \cdot 5 = 74~.

Cho hai dãy số nguyên ~a_1, a_2, \ldots, a_n~ và ~b_1, b_2, \ldots, b_n~. FireGhost130104 thực hiện thao tác sau nhiều lần:

• Chọn ra một vị trí ~i~ (~1 \le i \le n~), sau đó đổi chỗ ~2~ số ~a_i~ và ~b_i~.

Gọi ~f(a)~, ~f(b)~ lần lượt là tổng ~\text{xor}~ của các số thuộc mảng ~a~, ~b~. Hãy giúp FireGhost130104 tìm cách thực hiện các thao tác trên sao cho ~f(a) + f(b)~ đạt giá trị nhỏ nhất nhé!

Input

Dòng đầu tiên chứa số nguyên dương ~n~ (~1 \le n \le 2 \times 10^5~) — độ dài của hai dãy số ~a~ và ~b~.

Dòng tiếp theo chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ (~0 \le a_i \le 10^{18}~) — các phần tử của dãy ~a~.

Dòng cuối cùng chứa ~n~ số nguyên ~b_1, b_2, \ldots, b_n~ (~0 \le b_i \le 10^{18}~) — các phần tử của dãy ~b~.

Output

Một số nguyên duy nhất chứa đáp án của bài toán: giá trị nhỏ nhất của ~f(a) + f(b)~.

Scoring

• Subtask ~1~ (~20~ điểm): ~n \le 20~

• Subtask ~2~ (~80~ điểm): không có ràng buộc gì thêm.

Sample Input 1

3
2 3 7
4 1 5

Sample Output 1

6

Notes

Ở test ví dụ trên, ta có thể thực hiện thao tác đổi chỗ ~(a_2, b_2)~ và ~(a_3, b_3)~. Khi đó, ~a = [2, 1, 5]~ và ~b = [4, 3, 7]~, vì vậy ~f(a) + f(b) = 2 \oplus 1 \oplus 5 + 4 \oplus 3 \oplus 7 = 6 + 0 = 6~.