Một hệ thống lưu trữ chỉ giữ các tài liệu ở dạng nén. Mỗi tài liệu là một xâu gồm các chữ cái tiếng Anh in thường, được nén bằng cách gom những ký tự giống nhau đứng liền nhau thành từng khối: mỗi khối gồm một ký tự ~c~ và một số nguyên dương ~k~, mô tả ~k~ ký tự ~c~ viết liên tiếp. Xâu ban đầu là các khối ghép nối tiếp nhau theo đúng thứ tự đã cho, ví dụ: tài liệu gồm ba khối (a, ~3~), (b, ~2~), (a, ~1~) mô tả xâu aaabba. Lưu ý: hai khối liền nhau của cùng một tài liệu vẫn có thể có cùng ký tự.

Vì các tài liệu gốc có thể dài tới hàng tỉ tỉ ký tự nên hệ thống không thể giải nén chúng ra. Xâu ~u~ đứng trước xâu ~v~ theo thứ tự từ điển nếu ~u~ là tiền tố thực sự của ~v~, hoặc tại vị trí đầu tiên mà hai xâu khác nhau, ký tự của ~u~ nhỏ hơn ký tự của ~v~.

Cho ~n~ tài liệu ở dạng nén, hãy sắp xếp chúng theo thứ tự từ điển tăng dần của xâu ban đầu.

Input

• Dòng đầu tiên: số nguyên ~n~ (~1 \le n \le 5 \cdot 10^4~) là số tài liệu.

• ~n~ dòng tiếp theo, dòng thứ ~i~ mô tả tài liệu thứ ~i~: đầu tiên là số nguyên dương ~m_i~ là số khối, tiếp theo là ~m_i~ cặp ~c~ ~k~ lần lượt mô tả các khối, trong đó ~c~ là một chữ cái tiếng Anh in thường và ~1 \le k \le 10^{18}~.

• Tổng số khối của tất cả các tài liệu không vượt quá ~10^5~.

• Xâu ban đầu của mỗi tài liệu đảm bảo không có ~5 \cdot 10^{18}~ ký tự giống nhau liền nhau.

Output

In ra trên một dòng ~n~ số nguyên cách nhau một dấu cách là chỉ số các tài liệu theo thứ tự từ điển tăng dần của xâu ban đầu. Nếu hai tài liệu có xâu ban đầu bằng nhau thì tài liệu có chỉ số nhỏ hơn được in trước.

Scoring

Sample Input 1

5
2 a 3 b 2
1 a 5
3 a 2 a 1 b 2
2 a 3 b 1
1 b 1

Sample Output 1

2 4 1 3 5

Notes

Năm tài liệu lần lượt là aaabb, aaaaa, aaabb, aaab và b (tài liệu ~3~ có hai khối đầu cùng ký tự a).

Xếp theo thứ tự từ điển: aaaaa, aaab, aaabb, aaabb, b. Tài liệu ~1~ và ~3~ có xâu bằng nhau nên tài liệu ~1~ được in trước.