Có ~n~ người tham gia một trò chơi trúng thưởng. Những người này được xếp thành một hàng ngang và được đánh số từ ~1~ đến ~n~. Ban tổ chức sễ thực hiện ~m~ lần quay số, lần thứ ~i~ sẽ quay ra số nguyên dương ~x_i~, số nguyên không âm ~y_i~ và một ký tự ~c_i~. Tất cả những người ở có số thứ tự chia cho ~x_i~ dư ~y_i~ sẽ được Ban tổ chức phát cho một ký tự ~c_i~. Sau khi tất cả các lần quay thưởng được hoàn tất, mỗi người sẽ phải sử dụng những ký tự được phát để tạo thành một xâu đối xứng. Những người thành công tạo được xâu đối xững từ các ký tự được cho sẽ chiến thắng và nhận được số tiền thưởng lớn từ Ban tổ chức.

Bạn được biết các giá trị ~n, m~ và các bộ giá trị ~(x_i, y_i, c_i)~. Hãy xác định xem có bao nhiêu người có thể giành chiến thắng trong trò chơi lần này.

INPUT

Dòng đầu tiên chứa ba số nguyên dương ~n~, ~m~ (~1 \le n, m \le 2 \times 10^5~).

~m~ dòng tiếp, mỗi dòng gồm hai số nguyên không âm ~x_i, y_i~ và một ký tự ~c_i~ thuộc bảng chữ cái tiếng Anh in thường (~1 \le x_i \le n~, ~0 \le y_i \le x_i~).

OUTPUT

Số thứ tự của những người chơi có thể chiến thắng được in theo thứ tự tăng dần.

SAMPLE INPUT 1

5 4
2 1 a
2 0 b
3 2 a
4 2 b

SAMPLE OUTPUT 1

5

Giải thích:

• Các lượt quay thưởng được diễn ra như sau:

• Cả ~5~ người đều có khả năng chiến thắng:
  • Người thứ nhất và thứ ba có thể tạo ra xâu a.
  • Người thứ tư có thể tạo ra xâu b.
  • Người thứ năm có thể tạo ra xâu aa.
  • Người thứ hai tạo ra xâu bab.

SUBTASKS