Cho hai dãy số nguyên không âm \(l_1, l_2, \ldots l_n\) và \(r_1, r_2, \ldots, r_n\). Bạn cần xử lý \(q\) truy vấn thuộc một trong ba loại sau:

• L u v c: Gán mọi phần tử \(l_u, l_{u + 1}, \ldots, l_v\) bằng giá trị \(c\).
• R u v c: Gán mọi phần tử \(r_u, r_{u + 1}, \ldots, r_v\) bằng giá trị \(c\).
• Q u v: Bạn cần giải bài toán đếm sau:
  • xét các bộ số nguyên không âm \((x, y, i, j)\) thỏa mãn đồng thời các điều kiện:
    • \(u \le i < j \le v\)
    • \(l_i \leq x \leq r_i\)
    • \(l_j \leq y \leq r_j\)
  • Gọi \(c_0\) là số bộ \((x, y, i, j)\) thỏa mãn các điều kiện kể trên đồng thời số bit \(1\) trong biểu diễn nhị phân của \(x \oplus y\) là một số chẵn.
  • Gọi \(c_1\) là số bộ \((x, y, i, j)\) thỏa mãn các điều kiện kể trên đồng thời số bit \(1\) trong biểu diễn nhị phân của \(x \oplus y\) là một số lẻ.
  • Hãy tính \(c_0\) và \(c_1\).

Dữ liệu đảm bảo, trong mọi thời điểm, \(l_i \leq r_i\) với mọi \(1 \leq i \leq n\). Hãy xử lý các truy vấn trên.

Nhắc lại, phép toán \(\oplus\) (xor) đối với bit được định nghĩa như sau:

• \(0 \oplus 0 = 0\),
• \(1 \oplus 0 = 1\),
• \(0 \oplus 1 = 1\),
• \(1 \oplus 1 = 0\).

Phép toán \(\oplus\) đối với các số có nhiều hơn một bit được thực hiện theo từng bit. Ví dụ:

• \(2 \oplus 3 = 1\) \((10_2 \oplus 11_2 = 01_2)\),
• \(2 \oplus 5 = 7\) \((010_2 \oplus 101_2 = 111_2)\),
• \(5 \oplus 5 = 0\) \((101_2 \oplus 101_2 = 000_2)\).

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) (\(1 \le n, q \le 3 \cdot 10^5\)).
• Trong \(n\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(l_i\) và \(r_i\) (\(0 \le l_i \le r_i < 2^{60}\)), là các giá trị ban đầu của hai dãy.
• \(q\) dòng cuối cùng, mỗi dòng mô tả một truy vấn theo một trong ba định dạng:
  • L u v c
  • R u v c
  • Q u v
    (với \(1 \le u \le v \le n\) và \(0 \le c < 2^{60}\))

Output

Với mỗi truy vấn loại \(3\), in ra trên một dòng hai số nguyên lần lượt là phần dư của \(c_0\) và \(c_1\) khi chia cho \(10^9 + 22071997\).

Scoring

• Subtask \(1\) (\(5\) điểm): \(n, q \le 40\) và trong mọi thời điểm \(0 \le l_i \le r_i \le 90\).
• Subtask \(2\) (\(23\) điểm): \(n, q \le 200\) và trong mọi thời điểm \(0 \le l_i \le r_i \le 7000\).
• Subtask \(3\) (\(17\) điểm): \(n, q \le 500\).
• Subtask \(4\) (\(19\) điểm): Trong mọi thời điểm, \(l_1 = l_2 = \ldots = l_n = 0\) và tồn tại các số nguyên không âm \(e_1, e_2, \ldots e_n\) sao cho \(r_i = 2^{e_i} - 1\) với mọi \(1 \leq i \leq n\).
• Subtask \(5\) (\(19\) điểm): Không có truy vấn loại \(1\) và \(2\).
• Subtask \(6\) (\(17\) điểm): Không có ràng buộc gì thêm.

Example

3 3
1 2
3 4
5 6
Q 1 3
R 1 2 4
Q 1 3

4 8
8 12