Now the elections are over and Bico is elected as the president of the Mystic Empire of Tularis (METU). There are \(\mathbf{N}\) people in METU. To get elected, Bico promised everyone at least one cup of ice cream. On top of that, he made \(\mathbf{M}\) more promises to the people of METU. However, he wants to give as little ice cream as possible to keep himself some. He requests your help to calculate an optimal distribution.

Each promise represents a relation between two people, \(\mathbf{a}\) and \(\mathbf{b}\) (where \(\mathbf{a} \neq \mathbf{b}\)) with the comparison operator \(\mathbf{c}\). The comparison operator can be one of the following:

• =, meaning that \(\mathbf{a}\) and \(\mathbf{b}\) should get the same amount of ice cream.
• >, meaning that \(\mathbf{a}\) should get more ice cream than \(\mathbf{b}\).

Also, Bico needs to give each person at least \(1\) unit of ice cream. Help Bico allocate the minimum amount of ice creams for each person so that all the promises are kept.

There is no cycle in the promises with the second type of promises (>). So Bico can always allocate a finite amount of ice cream for each person. There can be cycles with the first type of promises (=). There can only be one type of promise for any given pair of people.

Input

In the first line, there are two integers \(\mathbf{N}\) and \(\mathbf{M}\), the number of people and the number of promises respectively.

In the following \(\mathbf{M}\) lines, each line contains three integers \(\mathbf{a}\), \(\mathbf{b}\) and \(\mathbf{c}\). The \(\mathbf{i}\)-th line represents the \(\mathbf{i}\)-th promise, which means that \(\mathbf{a}\) and \(\mathbf{b}\) have the relation \(\mathbf{c}\).

• \(2 \leq \mathbf{N} \leq 10^5\)
• \(2 \leq \mathbf{M} \leq 3 \cdot 10^5\)
• \(1 \leq \mathbf{a_i}, \mathbf{b_i} \leq \mathbf{N}\)

Output

In one line, print \(\mathbf{N}\) integers, the minimum amount of ice cream you need to allocate for each of the \(\mathbf{N}\) people.

Examples

Input 1:

5 4
1 2 =
3 2 >
4 3 >
5 4 >

Output 1:

1 1 2 3 4

Input 2:

5 5
1 2 >
3 2 >
3 4 >
5 4 >
5 3 >

Output 2:

2 1 2 1 3

Explanation

Input 1: The following distribution is optimal:

• Person 1 and 2 get \(1\) cup of ice cream each. (Promise 1)
• Person 3 gets \(2\) cups of ice creams. (1 more than person 2, promise 2)
• Person 4 gets \(3\) cups of ice creams. (1 more than person 3, promise 3)
• Person 5 gets \(4\) cups of ice creams. (1 more than person 4, promise 4)