Given N strings, print the rank of the strings when sorted in lexicographical order. Rank of a string is defined as the position of string in the input starting from 1. No string is repeated in the input.

Input

First line contains N, the number of strings. The next N lines contain one string S per line.

Output

Print N integers one per line denoting the rank of strings.

Constraints

N = 100000

|S| = 20

Strings are made up lowercase letters only.

Example

Input:
4
z 
b
a
c

Output:
3
2
4
1