Uolevi has recently gotten obsessed with sorting. He has an array consisting of a permutation of the integers 1 \cdots n, and can't wait to start sorting its intervals. For extra challenge, Uolevi tied a scarf around his head, preventing him from seeing the numbers. After getting bored with sorting intervals, Uolevi wants to know what the final array looks like. Can you tell him?

Input

The first line of input contains integers n q: The size of Uolevi's array, and the number of intervals Uolevi sorts.

The second line contains n integers: the initial order of Uolevi's array.

q lines follow. Each contains three integers a b d. If d = 1, Uolevi sorts interval [a, b] into increasing order. If d = -1, Uolevi sorts the interval into decreasing order.

Output

Output the array after Uolevi has finished sorting intervals.

Constraints

• 1 \leq n, q \leq 4 * 10^{5}
• 1 \leq a \leq b \leq n

Example

Input:

5 3
5 3 4 1 2
1 3 1
3 5 1
2 4 -1

Output:

3 4 2 1 5

Explanation:

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

are the contents of the array initially and after every update.