Determining the Ranking of Coins

Benson has \(n\) coins of distinct weights and a balance scale. In each weighing, two coins \(x\) and \(y\) are placed on the scale and it is determined whether \(x\) is heavier than \(y\) (denoted by \(x > y\)).

The rank of a coin \(x\) is defined as the number of coins that are not heavier than \(x\) (including \(x\) itself). For example, the lightest coin has a rank of \(1\), the second lightest coin has a rank of \(2\), and the heaviest coin has a rank of \(n\).

A coin's rank is said to be determined if and only if, based on the weighing results obtained so far, its exact rank can be uniquely deduced. Your task is to determine, for each coin, the index of the weighing (1-indexed) at which its rank is first determined. If a coin's rank is never determined after all weighings, output \(-1\) for that coin.

Note: After each weighing, using the transitive property of the comparisons, one can deduce extra relations. For a coin \(i\), let \(L_i\) be the number of coins that are definitely lighter (i.e. for which it is known that \(i\) is heavier than them) and let \(H_i\) be the number of coins that are definitely heavier (i.e. for which it is known that they are heavier than \(i\)). The coin's rank will be uniquely determined if and only if:

\(L_i + 1 = n - H_i\)

inputFormat

The input begins with a line containing two integers \(n\) and \(m\) \( (1 \leq n \leq 100,\ 1 \leq m \leq 1000)\) which represent the number of coins and the number of weighings, respectively.

Each of the next \(m\) lines contains two integers \(x\) and \(y\) (\(1 \le x, y \le n,\ x \neq y\)) followed by a character. If the character is '>', it means that coin \(x\) is heavier than coin \(y\). Otherwise, if the character is '<', then coin \(y\) is heavier than coin \(x\).

outputFormat

Output a single line with \(n\) space-separated integers. The \(i\)-th integer should be the 1-indexed weighing number at which coin \(i\)'s rank is first determined. If the coin's rank is never determined by the end of the weighings, output \(-1\) for that coin.

sample

3 3
2 1 >
3 2 >
3 1 >

2 2 2