Xâu đối xứng

Tác giả:

Dạng bài

Ngôn ngữ cho phép

Assembly, Awk, C, C#, C++, Clang, Cobol, D, ~~Groovy~~, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, Output, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, ~~Swift~~

Điểm: 1900 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: PALIND.inp Output: PALIND.out

Có $N$ xâu $s_1, s_2, \dots, s_n$ ban đầu rỗng và $Q$ truy vấn. Truy vấn thứ $i$ gồm hai số nguyên $X_i, Y_i$ và ký tự $C_i$, yêu cầu thêm ký tự $C_i$ vào các xâu $s_j$ với mọi $j$ chia $X_i$ dư $Y_i$. Cho biết sau khi tất cả các truy vấn được thực hiện, có những xâu $s_j$ nào thỏa mãn: tồn tại cách sắp xếp lại các ký tự trong xâu để được một xâu đối xứng.

Input

Dòng đầu tiên gồm hai số nguyên dương $N, Q$ ($1 \le N, Q \le 2 \cdot 10^5$).
$Q$ dòng tiếp theo, mỗi dòng gồm hai số nguyên $X_i, Y_i$ và một ký tự $C_i$ thuộc bảng chữ cái tiếng Anh ($0 \le Y_i < X_i \le n$).

Output

Ghi ra tệp văn bản PALIND.out một dòng duy nhất gồm các giá trị $j$ thỏa mãn theo thứ tự tăng dần.

Example

Test 1

Input

Output

1 2 3 4 5

Note

Các ký tự được thêm vào như sau:

	1	2	3	4
$s_1$	a
$s_2$		b	a	b
$s_3$	a
$s_4$		b
$s_5$	a		a

Sau khi tất cả các ký tự đã được thêm, $s_1$ và $s_3$ có thể được sắp xếp thành a, $s_2$ có thể được sắp xếp thành bab, $s_4$ có thể được sắp xếp thành b, $s_5$ có thể được sắp xếp thành aa.

Scoring

$12\%$ số điểm có $c_i = $ a với mọi truy vấn.
$42\%$ số điểm khác có $n, m \le 2000$.
$18\%$ số điểm khác có $c_i = $ a hoặc $c_i = $ b với mọi truy vấn.
$28\%$ số điểm còn lại không có giới hạn gì thêm.

Bình luận

Tải bình luận...

Không có bình luận nào.

Kỳ thi:

Contest ôn thi HSG9 và giao lưu lớp 10 Chuyên (lần 2) (21 Tháng 11., 2025)

	1	2	3	4
\(s_1\)	a
\(s_2\)		b	a	b
\(s_3\)	a
\(s_4\)		b
\(s_5\)	a		a