Cho 1 bảng màu xen kẽ† gồm \(n\) hàng và \(m\) cột.
Các hàng được đánh số từ 1 đến n từ trên xuống dưới.
Các cột được đánh số từ 1 đến m từ trái qua phải.
Ô ở hàng \(i\), cột \(j\) là ô \(a_{ij}\) - được tô màu đỏ hoặc màu xanh
Ô ở bên trái, dưới cùng được tô màu xanh.

† Bảng màu xen kẽ tức là một bảng sao cho không có bất kì hai ô liền kề‡ nào có cùng 1 màu
‡ Hai ô được gọi là liền kề nếu chúng có chung 1 cạnh

Bảng màu xen kẽ gồm \(3\) hàng và \(3\) cột:

Input:

• Dòng đầu tiên nhập vào 3 số nguyên dương \(n, m, q\) \((n, m <= 10^{18}; q <= 10^6)\) - lần lượt là số hàng, số cột và số lượng truy vấn.
• \(q\) dòng tiếp theo, dòng thứ \(i\) nhập vào 2 số nguyên dương \(r_i, c_i\) \((r_i <= n; c_i <= m)\)

Output:

• Với truy vấn thứ \(i\), hãy in ra "RED" nếu ô \(a_{r_i, c_i}\) được tô màu đỏ hoặc in ra "BLU" trong trường hợp ngược lại

Lưu ý dữ liệu đầu vào có thể rất lớn. Trong một số trường hợp, hãy thêm duy nhất một dòng ios_base::sync_with_stdio(false); cin.tie(NULL); vào mã nguồn để xử lí một số trường hợp bài làm có kết quả là Time Limit Exceeded. Đọc thêm tại đây.

Example

3 3 3
1 1
2 2
2 3

BLU
BLU
RED

Subtask \(1\) (\(50\)% số điểm): \(n * m \leq 10^6,\) \(q \leq 10^6\)
Subtask \(2\) (\(50\)% số điểm): \(n, m \leq 10^{18},\) \(q \leq 10^6\)

Doraemon rất thích ăn buffet lẩu ở Kichi-Kichi. Ở đây có \(n\) món ăn với số lượng vô hạn - mỗi món có thể được ăn vô số lần (có thể ăn \(0\) lần). Các món ăn được đánh số từ \(1\) đến \(n\), món thứ \(i\) có khối lượng là \(a_i\). Tổng khối lượng các món mà Doraemon có thể ăn không vượt quá \(m\).

Input:

• Dòng đầu tiên gồm một số nguyên dương \(t\) (\(t \leq 100\)) - số lượng truy vấn.
• \(2 * t\) dòng tiếp theo, mỗi truy vấn nhập vào hai dòng:
  • Dòng đầu tiên nhập vào hai số nguyên dương \(n\), \(m\) (\(n, m \leq 10^4\)) - số món ăn và khối lượng đồ ăn tối đa mà Doraemon có thể ăn.
  • Dòng tiếp theo, nhập vào \(n\) số nguyên dương \(a_1, a_2, a_3, ..., a_n\) (\(1 \leq a_i \leq 10^5\) \(∀\) \(1 \leq i \leq n\)). - khối lượng của từng món ăn.

Output:

• Với mỗi truy vấn, in ra \(m\) số. Số thứ \(i\) là \(1\) nếu có thể ăn sao cho tổng khối lượng các món ăn là \(i\) và in ra \(0\) trong trường hợp ngược lại.

Ở mỗi subtask, luôn đảm bảo rằng tổng của \(n\) trong các truy vấn không vượt quá \(N\).

Example

2
3 20
3 6 9
2 10
4 5

0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 
0 0 0 1 1 0 0 1 1 1

Subtask \(1\) (\(50\)% số điểm): \(t \leq 10,\) \(N \leq 20,\) \(m \leq 10^4\)
Subtask \(2\) (\(20\)% số điểm): \(t \leq 100,\) \(N \leq 10^3,\) \(m \leq 10^3\)
Subtask \(3\) (\(30\)% số điểm): \(t \leq 100,\) \(N \leq 10^4,\) \(m \leq 10^4\)

Input:

• Dòng đầu tiên nhập vào một số nguyên dương \(t\) - số lượng truy vấn.
• \(t\) dòng tiếp theo, mỗi dòng nhập vào một số nguyên dương \(n\) (\(2 \le n\))

Output:

• Với mỗi truy vấn, hãy in ra số n sau khi đã phân tích thành thừa số nguyên tố.
• In ra kết quả dưới dạng luỹ thừa. VD: 8 = 2^3, 12 = 2^2*3, ...

Example

5
6
7
12
15
18

2*3
7
2^2*3
3*5
2*3^2

Subtask \(1\) (\(50\)% số điểm): \(t <= 10,\) \(n <= 10^6\)
Subtask \(2\) (\(20\)% số điểm): \(t <= 10,\) \(n <= 10^{12}\)
Subtask \(2\) (\(30\)% số điểm): \(t <= 10^6,\) \(n <= 2*10^7\)

Cho dãy \(a\) gồm \(n\) số nguyên dương \(a_1, a_2, a_3, ..., a_n\).
Có \(3\) loại truy vấn:

• \(1\) \(k\) \(x:\) Tăng \(a_k\) lên \(x\) đơn vị (\(1 \leq x \leq 10^9\)).
• \(2\) \(k\) \(x:\) Đặt \(a_k = a_k\) XOR \(x\).
• \(3\) \(l\) \(r:\) Đếm số lượng số nguyên \(k\) (\(l \leq k \leq r\)) mà \(a_l\) \(XOR\) \(a_{l + 1}\) \(XOR\) \(a_{l + 2}\) \(XOR\) \(...\) \(XOR\) \(a_{k}\) là số lẻ.

Input:

• Dòng đầu tiên nhập vào hai số nguyên dương \(n,\) \(q\) - lần lượt là số phần tử dãy \(a\) và số lượng truy vấn.
• Dòng thứ hai là \(n\) số nguyên dương \(a_1, a_2, a_3, ..., a_n\) (\(1 \leq a_i \leq 10^9\) \(∀\) \(1 \leq i \leq n\)).
• \(q\) dòng tiếp theo, mỗi dòng nhập ba số nguyên là một trong ba truy vấn loại trên.

Output:

• Với mỗi truy vấn loại \(3\), hãy in ra kết quả theo yêu cầu của đề bài.

Example

5 5
1 4 5 8 9
3 1 5
1 2 3
3 1 5
2 3 9
3 1 5

3
3
2

Subtask \(1\) (\(50\)% số điểm): \(n <= 10^4, q <= 10^3\).
Subtask \(2\) (\(20\)% số điểm): \(n <= 10^6, q <= 10^6\). Chỉ bao gồm các truy vấn loại \(3\).
Subtask \(3\) (\(30\)% số điểm): \(n <= 10^6, q <= 10^6\).