Hộp chứa thẻ · CODER HUSC

Time limit: 1.0 s
Memory limit: 256 MB
Points: 1,000
AC rate: 45.9%
Solvers: 28

Có $N$ ~N~ chiếc hộp dùng để chứa các tấm thẻ (các hộp được đánh số từ $1$ ~1~ đến $N$ ~N~), trên mỗi tấm thẻ được ghi một giá trị nguyên. Ban đầu toàn bộ hộp đều rỗng. Thực hiện $Q$ ~Q~ truy vấn thuộc một trong ba loại sau:

Loại $1$ ~1~ có dạng 1 X Y $($ ~(~ $1 \le X \le 2.10^5$ ~1 \le X \le 2.10^5~, $1 \le Y \le N$ ~1 \le Y \le N~ $)$ ~)~: Thêm một tấm thẻ ghi giá trị $X$ ~X~ vào hộp thứ $Y$ ~Y~.
Loại $2$ ~2~ có dạng 2 Y $($ ~(~ $1 \le Y \le N$ ~1 \le Y \le N~ $)$ ~)~: In ra giá trị của các tấm thẻ có trong hộp thứ $Y$ ~Y~, theo thứ tự tăng dần. Nếu hộp thứ $Y$ ~Y~ rỗng, in ra $-1$ ~-1~.
Loại $3$ ~3~ có dạng 3 X $($ ~(~ $1 \le X \le 2.10^5$ ~1 \le X \le 2.10^5~ $)$ ~)~: In ra chỉ số của các hộp có chứa tấm thẻ ghi giá trị $X$ ~X~, theo thứ tự tăng dần. Nếu không có hộp nào, in ra $-1$ ~-1~.

Input

Dòng đầu tiên chứa hai số nguyên $N$ ~N~ và $Q$ ~Q~ $(1 \le N,Q \le 2.10^5)$ ~(1 \le N,Q \le 2.10^5)~.
$Q$ ~Q~ dòng tiếp theo, mỗi dòng chứa một trong ba loại truy vấn trên.
Dữ liệu đảm bảo có ít nhất một truy vấn loại $2$ ~2~ hoặc ít nhất một truy vấn loại $3$ ~3~.

Output

Với mỗi truy vấn loại $2$ ~2~ và loại $3$ ~3~, in ra kết quả trên một dòng.

Examples

Sample Input

Sample Output

-1
1 1 2
3 4

Scoring

Subtask $1$ ~1~ với $500$ ~500~ điểm: $N,Q \le 1000$ ~N,Q \le 1000~ và $X \le 1000$ ~X \le 1000~ với mọi truy vấn loại $1$ ~1~ và loại $3$ ~3~
Subtask $2$ ~2~ với $500$ ~500~ điểm: Không có ràng buộc gì thêm

Comments

You need to sign in to write comments, reply and vote.