Mật mã an toàn


Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 1G

Problem type

Tổ chức Rebellion đang muốn gửi một mật mã cho một vài chiến binh đang làm nhiệm vụ tại quá khứ. Họ cần nhanh chóng nhận lệnh và thực hiện thành công trước khi Don Armage nhận ra và tàn phá. Vì mật mã phải vượt thời gian nên phải đảm bảo một số quy tắc an toàn để tránh mất dữ liệu. Biết rằng mất mã đó là một xâu kí tự gồm các kí tự latin thường. Có $Q$ quy tắc được đặt ra, mỗi quy tắc là một bộ 3 số $i,j,k$, xâu cần đảm bảo $s[i..i+k-1] \ge s[j..j +k-1]$. Chỉ huy Shou Rinpou đã soạn ra mật mã. Ông định giao Raptor 283 kiểm tra các quy tắc. Nhưng lúc này, Raptor 283 đang cùng 4 thành viên khác thực hiện một nhiệm vụ quan trọng trên Trái Đất. Vì vậy, hãy giúp Shou Rinpou kiểm tra xem, có bao nhiêu quy tắc đã đảm bảo và liệt kê các quy tắc chưa đảm bảo.

Dữ liệu

  • Dòng đầu tiên chứa xâu kí tự $S \ (|S| \le 10^5)$;
  • Dòng tiếp theo chứa số nguyên dương $Q \ (Q \le 10^5)$;
  • $Q$ dòng tiếp theo, mỗi dòng chứa ba số nguyên dương $i,j,k \ (1 \le i,j,k,max(i+k-1,j+k-1) \le N)$.

Kết quả

  • Dòng đầu tiên in số lượng quy tắc đã đảm bảo;
  • Dòng tiếp theo, in các quy tắc chưa đảm bảo theo thứ tự tăng dần, mỗi quy tắc cách nhau bởi một dấu cách.

Chấm điểm

50; $|S|\le10^3;Q\le 10^2$. 50; Không có giới hạn gì thêm.

Ví dụ

Ví dụ 1

input

echothroughouttheuniversealrightlucky
5
1 5 7
7 2 3
6 7 2
10 12 7
15 8 3

output

2
1
3
4

Comments

There are no comments at the moment.