Các tờ giấy ghi từ được bỏ vào một chiếc mũ. Khi đến lượt, một đội sẽ bốc ra một tờ và cố gắng đoán đúng từ trên đó. Nếu đoán đúng, đội được +1 điểm và tờ giấy đó bị loại khỏi trò chơi. Nếu hết thời gian mà chưa đoán đúng, tờ giấy được bỏ lại vào mũ và có thể được bốc lại ở những lượt sau. Trò chơi kết thúc khi mọi tờ giấy đều đã bị loại (tức là mọi từ đều đã được đoán đúng).

Người dẫn chương trình có biên bản gồm ~m~ lần bốc từ, nhưng do sự cố chỉ còn lại 2 cột: đội chơi và từ mà đội đó phải đoán. Thứ tự các bản ghi vẫn được giữ nguyên.

Yêu cầu

Từ biên bản còn lại, hãy xác định số điểm mà mỗi đội ghi được.

Nhận xét quan trọng: vì trò chơi kết thúc sau ~m~ lần bốc và mọi tờ giấy đều đã bị loại, nên với mỗi từ xuất hiện trong biên bản, lần xuất hiện cuối cùng của từ đó chắc chắn là lần đoán đúng (nếu không đúng thì tờ giấy sẽ quay lại mũ và từ đó phải xuất hiện thêm lần nữa). Do đó, đội ghi điểm cho một từ chính là đội xuất hiện ở lần cuối cùng của từ đó.

Dữ liệu

• Dòng đầu chứa hai số nguyên ~n~ và ~m~ (~1 \le n, m \le 10^5~).

• Mỗi dòng trong ~m~ dòng tiếp theo chứa:

  • một số nguyên ~\text{team}_j~ (đội thực hiện lần bốc thứ ~j~, ~1 \le \text{team}_j \le n~),
  • và một xâu ~\text{word}_j~ chỉ gồm chữ cái Latin thường, độ dài không quá ~10~.

Kết quả

In ra ~n~ số nguyên trên một dòng, số thứ ~i~ là số điểm đội ~i~ ghi được.

Ví dụ

Ví dụ 1

Input

2 3
1 hat
1 shirt
2 hat

Output

1 1

Giải thích

Ví dụ 1

• Từ ~shirt~ chỉ xuất hiện một lần, nên lần đó là đoán đúng: đội ~1~ được 1 điểm.
• Từ ~hat~ xuất hiện hai lần, lần cuối là bởi đội ~2~, nên đội ~2~ là đội đoán đúng và được 1 điểm. Vì vậy kết quả là ~[1, 1]~.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le n, m \le 10^5~
• ~1 \le \text{team}_j \le n~
• ~\text{word}_j~ chỉ gồm chữ cái Latin thường, ~|\text{word}_j| \le 10~