Cho số ~n~ và dãy số gồm ~n + 1~ số nguyên dương phân biệt ~a_1, a_2, \ldots, a_{n + 1}~ có giá trị trong đoạn ~[1, 2 \times n]~.

Bạn hãy tìm ra hai số trong dãy là hai số nguyên tố cùng nhau. Hai số nguyên được gọi là nguyên tố cùng nhau nếu chúng có ước chung lớn nhất là ~1~.

Input

Dòng thứ nhất chứa một số nguyên dương ~n~ (~2 \le n \le 10^5~).

Dòng thứ hai chứa ~n + 1~ số nguyên dương phân biệt ~a_1, a_2, \ldots, a_{n + 1}~ (~1 \le a_i \le 2 \times n~, ~\forall 1 \le i \le n + 1~).

Output

In ra hai giá trị có trong dãy số là cặp số nguyên tố cùng nhau. Nếu có nhiều cặp số thỏa mãn thì in ra một cặp bất kì. Nếu không có cặp số nào thỏa mãn thì in ra hai số ~-1~.

Scoring

Sample Input 1

6
2 12 7 10 9 6 4

Sample Output 1

7 9

Cho ~n~ số nguyên ~a_1, a_2, \dots, a_n~ và ~m~ số nguyên ~b_1, b_2, \dots, b_m~. Tính giá trị của:

$$\sum_{i = 1}^n \sum_{j = 1}^m {a_i \; \text{AND} \; (a_i \; \text{XOR} \; b_j)}$$

Chi tiết về phép toán ~\text{AND}~ và ~\text{XOR}~ có thể tìm hiểu thêm ở đây.

Input

• Dòng thứ ~1~ bao gồm ~2~ số nguyên dương ~n~ và ~m~ lần lượt là độ dài mảng ~a~ và ~b~. ~(1 \le n, m \le 10^5)~.

• Dòng thứ ~2~ gồm ~n~ số nguyên ~a_1, a_2, \dots, a_n~. (~0 \le a_i < 2^{20}~).

• Dòng thứ ~3~ gồm ~m~ số nguyên ~b_1, b_2, \dots, b_m~. (~0 \le b_j < 2^{20}~).

Output

• ~1~ số duy nhất là giá trị biểu thức trên.

Scoring

Sample Input 1

2 2
1 2
3 4

Sample Output 1

3

Notes

Ở test ví dụ, ta có: ~x \in~ ~\{1, 2\}~ và ~y \in~ ~\{3,4\}~, mà:

• ~1 \; \text{AND} \;~ (~1 \; \text{XOR} \; 3~) ~= 0~.

• ~1 \; \text{AND} \;~ (~1 \; \text{XOR} \; 4~) ~= 1~.

• ~2 \; \text{AND} \;~ (~2 \; \text{XOR} \; 3~) ~= 0~.

• ~2 \; \text{AND} \;~ (~2 \; \text{XOR} \; 4~) ~= 2~.

Tổng của ~4~ giá trị tìm được là ~3~.

Tìm số dãy nhị phân ~s~ thỏa mãn tất cả các điều kiện sau:

• ~s~ chứa ít nhất ~1~ chữ số ~0~ và ~1~ chữ số ~1~.

• ~s~ chứa tối đa ~a_0~ chữ số ~0~ và ~a_1~ chữ số ~1~.

• Khi chia ~s~ thành các đoạn liên tiếp chứa toàn chữ số ~0~ hoặc ~1~, độ dài các dãy chứa toàn chữ số ~0~ không nhỏ hơn ~b_0~ và độ dài các dãy chứa toàn chữ số ~1~ không nhỏ hơn ~b_1~.

Ví dụ với ~b_0 = 3~ và ~b_1 = 2~ thì:

• ~1100001111000~ = [~11~, ~0000~, ~1111~, ~000~] là dãy thoả mãn

• ~00011100~ = [~000~, ~111~, ~00~] không thoả mãn, do đoạn con ~00~ có độ dài nhỏ hơn ~b_0~.

In ra kết quả ~\text{mod}~ ~10^9 + 7~.

Input

Dòng đầu tiên gồm hai số ~a_0~ và ~a_1~ (~1 \leq a_0, a_1 \leq 10^6~), số chữ số tối đa của ~0~ và ~1~.

Dòng thứ hai gồm hai số ~b_0~ và ~b_1~ (~1 \leq b_0 \leq a_0~, ~1 \leq b_1 \leq a_1~).

Output

Ghi ra một số duy nhất là đáp án của đề bài.

Scoring

Sample Input 1

7 13
7 12

Sample Output 1

4

Đây là bài tương tác, hãy đọc hướng dẫn làm bài tương tác ở đây.

Cho một bảng gồm ~N~ dòng và ~N~ cột, mỗi ô trên bảng được điền một giá trị có giá trị tuyệt đối không quá ~10^6~. Gọi ô ~(x, y)~ là ô nằm tại dòng thứ ~x~ từ trên xuống và cột thứ ~y~ từ trái sang của bảng, bạn phải trả lời ~Q~ truy vấn, mỗi truy vấn yêu cầu bạn cần tính tổng giá trị các ô thuộc hình chữ nhật con được giới hạn bởi góc trái trên ~(x_1, y_1)~ và góc phải dưới ~(x_2, y_2)~ ~(1 \leq x_1 \leq x_2 \leq N, 1 \leq y_1 \leq y_2 \leq N)~. Đầu tiên bạn cần khai báo mảng ~S~ là cấu trúc dữ liệu chứa ~M~ đoạn thẳng bằng cú pháp sau:

~M~

~L_1, R_1~

~…~

~L_M, R_M~

Đoạn thẳng thứ ~i~ trong mảng ~S~ sẽ được giới hạn bởi ~2~ đầu mút là ~L_i~ và ~R_i~. Ở đây, bạn được phép tùy ý lựa chọn các tham số như ~M~, ~L_i~ hay ~R_i~ miễn là chúng thỏa mãn ~3~ điều kiện sau:

• ~1 \leq M \leq N~.

• ~1 \leq L_i \leq R_i \leq N~.

• Tổng độ dài các đoạn thẳng trong ~S~ không quá ~10^6~.

Ràng buộc:

• ~1 \leq N \leq 100000~

• ~1 \leq Q \leq 100~

Interaction

1. Dòng đầu tiên của đầu vào là số nguyên dương ~N~ thể hiện kích thước của bảng.

2. Sau khi đọc ~N~, bạn cần khai báo mảng ~S~ bằng cú pháp đã cho như trên:

    M
    L[1] R[1]
    ...
    L[M] R[M] 
   

3. Tiếp theo, máy chấm sẽ cho bạn biết ~Q~ là số truy vấn cần trả lời.

4. Máy chấm sẽ cho bạn ~1~ truy vấn gồm ~4~ số đại diện cho tọa độ góc trái trên và phải dưới của hình chữ nhật con :

    X1 Y1 X2 Y2 
   

5. Sau đó bạn được quyền hỏi máy chấm không quá ~1024~ câu hỏi dưới dạng:

    ? S1 S2 
   

   Từ mảng ~S~ đã chọn, máy chấm trả về kết quả là tổng giá trị các ô thuộc hình chữ nhật con có góc trái trên là ~(L_{S_1}, L_{S_2})~ và góc phải dưới ~(R_{S_1}, R_{S_2})~.

6. Bạn phải in đáp án cho mỗi truy vấn như sau:

    ! SUM 
   

   Với ~SUM~ là tổng giá trị các ô thuộc hình chữ nhật con, nếu kết quả của bạn đúng thì máy chấm sẽ thực hiện thay đổi giá trị một số ô trên bảng rồi bạn biết truy vấn tiếp theo cần trả lời. Quá trình này lặp lại cho đến khi bạn trả lời hết ~Q~ truy vấn.

Scoring

Sample Input 1

3




3
2 1 2 2

35

40

3 1 3 1

42

1 2 1 3

7

5

6

Sample Output 1

3
1 1
2 2
3 3


? 2 1

? 2 2

! 75

? 3 1

! 42

? 1 1

? 1 2

? 1 3

! 11

Vũ và Việt mỗi người có một tập hợp các điểm có toạ độ thực trên mặt phẳng ~Oxy~, và mỗi tập đều là hợp của một số hình chữ nhật (có thể giao nhau). Mỗi người sẽ chọn hai điểm trong tập của mình một cách độc lập và ngẫu nhiên~^\dagger~. Nhiệm của bạn là tính giá trị kỳ vọng của khoảng cách Manhattan~^\ddagger~ giữa hai điểm được chọn.

~^\dagger~ Việc chọn ngẫu nhiên các điểm thoả mãn phân bố đều liên tục.

~^\ddagger~ Khoảng cách Manhattan giữa hai điểm ~(x_1,y_1)~ và ~(x_2,y_2)~ được định nghĩa là ~|x_1-x_2|+|y_1-y_2|~.

Input

Dòng đầu tiên gồm hai số nguyên ~n~ và ~m~ (~n,m\le 10^5~) — số hình chữ nhật lần lượt tạo nên tập điểm của Vũ và Việt.

Mỗi dòng trong ~n+m~ dòng tiếp theo gồm bốn số nguyên ~x_1,y_1,x_2,y_2~ (~-10^9\le x_1\le x_2\le 10^9~, ~-10^9\le y_1\le y_2\le 10^9~) — toạ độ đỉnh trái dưới ~(x_1,y_1)~ và phải trên ~(x_2,y_2)~ của hình chữ nhật. ~n~ hình chữ nhật đầu tiên và phần còn lại tạo nên lần lượt tập điểm của Vũ và Việt.

Các hình chữ nhật đã cho có thể suy biến. Cụ thể:

• Nếu ~x_1=x_2~ hoặc ~y_1=y_2~ thì hình chữ nhật suy biến thành một đoạn thẳng.

• Nếu ~x_1=x_2~ và ~y_1=y_2~ thì hình chữ nhật suy biến thành một điểm.

Output

In ra một dòng duy nhất chứa đáp án của bài toán chia dư cho ~10^9 + 7~. Cụ thể, gọi ~\frac{p}{q}~ là phân số tối giản biểu diễn kết quả, in ra ~ans~ sao cho ~ans \equiv \frac{p}{q} \pmod {10^9 + 7}~.

Scoring

Sample Input 1

1 1
0 0 0 0
1 1 1 1

Sample Output 1

2

Sample Input 2

1 1
2 0 2 4
0 2 4 2

Sample Output 2

2

Sample Input 3

1 1
0 0 1 1
1 1 2 2

Sample Output 3

2

Dế Mèn có một mảng hai chiều ~a~ kích thước ~n \times m~, trong độ mỗi ô ~a_{i,j}~ là một chữ số từ ~0~ đến ~9~.

Bạn được thực hiện các thao tác sau trên bảng (có thể làm ~0~, ~1~, hoặc nhiều lần):

• Đảo ngược thứ tự của các chữ số trên một hàng.

• Đảo ngược thứ tự của các chữ số trên một cột.

Cho biết số bảng khác nhau có thể tạo ra nếu áp dụng các thao tác trên. Vì đáp án có thể rất lớn, in ra đáp án ~\text{mod}~ ~10^9 + 7~.

Input

• Dòng đầu tiên nhập hai số nguyên ~n~ và ~m~ (~1 \le n, m \le 1000~).

• ~n~ dòng tiếp theo, dòng thứ ~i~ nhập ~m~ chữ số ~a_{i,1}, a_{i,2}, \dots, a_{i,m}~ liền kề nhau.

Output

In ra số bảng khác nhau có thể tạo ra nếu áp dụng các thao tác trên, modulo ~10^9 + 7~.

Scoring

Sample Input 1

2 2
12
12

Sample Output 1

6