Đâ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