Problem K
Gladiators

In the Roman Empire, gladiator fights were a popular sport. To conduct a fight, $N$ gladiators line up in a row, with positions numbered from $0$ to $N-1$. Each gladiator has a unique strength between $0$ and $N-1$. Then, a number of attacks will occur. During an attack, some gladiator starts running either to the right or to the left. They then defeat all gladiators they encounter whose strength is strictly less than the attacker’s. If the gladiator reaches the end of the line, either to the right or to the left, or encounters a stronger gladiator, they end their attack and return to the position they originally stood on. All defeated gladiators leave the line, leaving an empty spot behind. Defeated gladiators cannot stop future attacks or attack themselves.

You have now found a list of all attacks that took place during a certain fight. For each defeated gladiator, you now want to determine who defeated them.

Input

The first line of input contains the integers $N$ and $Q$ ($1 \leq N,Q \leq 3 \cdot 10^5$), the number of gladiators and the number of attacks.

The following line contains the $N$ integers $s_0, s_1, \dots , s_{N-1}$ ($0 \leq s_i \leq N-1$), the strengths of the gladiators. It is guaranteed that for each strength between $0$ and $N-1$, there exists exactly one gladiator with said strength.

Finally, $Q$ lines follow, each containing the integer $P$ and the character $D$ ($0 \leq P \leq N-1$, $D \in {<,>}$), which describes the position of a gladiator starting an attack, and the direction of the attack. These are given in the same order as the attacks occur. It is guaranteed that defeated gladiators never start an attack.

Output

Print $N$ integers on a single row: for each gladiator, print the position of the gladiator that defeated it. If a certain gladiator is never defeated, print $-1$ instead.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.

Explanation of Samples

In the first attack, the gladiator at position $1$ defeats the gladiator at position $2$. At position $3$, they encounter a stronger gladiator and thereby end their attack.

Then, the gladiator with strength $4$ at the far right attacks. They defeat all remaining gladiators except the one at the far left. Note that they do not defeat the gladiator at position $2$, since that one has already been defeated.

In the final attack, the gladiator with strength $5$ at position $0$ defeats the remaining gladiator. Since this gladiator is never defeated, you should output $-1$ at position $0$.

5 3
4 1 0 2 3
1 >
4 <
0 >

-1 4 1 4 0