Thi thử TS10 2024 - Ngày 3 - Bộ đề bài - LQDOJ: Le Quy Don Online Judge

#	Bài tập	Điểm	Thời gian:	Giới hạn bộ nhớ
1	Xanh - Đỏ	3 (p)	1.0s	256M
2	Kichi-Kichi	3 (p)	2.0s	256M
3	Factors	2 (p)	1.0s	256M
4	Range XOR Queries	2 (p)	2.5s	512M

1. Xanh - Đỏ

Điểm: 3 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

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 \leq 10^{18}; q \leq 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 \leq n; c_i \leq 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.

Note

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

Test 1

Input

Output

BLU
BLU
RED

Scoring

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

2. Kichi-Kichi

Điểm: 3 (p) Thời gian: 2.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

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 \cdot 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, \dots, a_n\) (\(1 \leq a_i \leq 10^5\) \(\forall\) \(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

Test 1

Input

Output

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

Scoring

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\)

3. Factors

Điểm: 2 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

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

Test 1

Input

Output

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

Scoring

Subtask \(1\) (\(50\%\) số điểm): \(t \le 10\), \(n \le 10^6\).
Subtask \(2\) (\(20\%\) số điểm): \(t \le 10\), \(n \le 10^{12}\).
Subtask \(3\) (\(30\%\) số điểm): \(t \le 10^6\), \(n \le 2\cdot 10^7\).

4. Range XOR Queries

Điểm: 2 (p) Thời gian: 2.5s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Cho dãy \(a\) gồm \(n\) số nguyên dương \(a_1, a_2, a_3, \dots, 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 \text{ XOR } a_{l+1} \text{ XOR } a_{l+2} \text{ XOR } \dots \text{ 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, \dots, a_n\) (\(1 \leq a_i \leq 10^9\) với mọi \(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

Test 1

Input

Output

3
3
2

Scoring

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