Little D has $n$ std::queue<int> objects, which he labels from $1$ to $n$.

Little D has different levels of preference for each queue. If a queue he does not like very much occupies too much memory, Little D becomes unhappy.

Specifically, if the size() of the $i$-th queue is greater than $a_i$, Little D will repeatedly perform pop() on that queue until its size() is less than or equal to $a_i$.

Currently, all these queues are empty. Little D finds this too monotonous, so he decides to perform some operations.

Each operation is described by l r x, which means performing a push(x) operation on all queues with indices in the range $[l, r]$. Of course, after each operation, Little D will use the method mentioned above to prevent these queues from occupying too much memory.

Little D's queues are magical, so he can perform each operation in $O(1)$ time.

He believes everyone's queues can do the same, so he presents this problem to you as a freebie.

To prove that you have indeed performed these operations, you need to output the number of distinct values currently present in the queues after each operation.

Input

The first line contains two positive integers $n$ and $m$, representing the number of queues and the number of operations, respectively.

The second line contains $n$ positive integers, where the $i$-th integer represents $a_i$.

The next $m$ lines each contain three positive integers l r x, where the $i$-th line represents the $i$-th operation.

Output

Output $m$ lines, each containing a non-negative integer representing the number of distinct values in all queues after the $i$-th operation.

Examples

Input 1

3 3
1 2 3
1 2 1
2 3 2
1 3 3

Output 1

1
2
2

Note 1

After the first operation, the queues become $\{1\}, \{1\}, \{\}$. The values present in the queues are $\{1\}$, for a total of $1$ distinct value.

After the second operation, the queues become $\{1\}, \{1, 2\}, \{2\}$. The values present in the queues are $\{1, 2\}$, for a total of $2$ distinct values.

After the third operation, the queues become $\{3\}, \{2, 3\}, \{2, 3\}$. The values present in the queues are $\{2, 3\}$, for a total of $2$ distinct values.

Subtasks

For all data, $n, m, a_i, x \leq 10^5$ and $l \leq r$.

There are $20$ test cases, each worth $5$ points. The $k$-th test case satisfies $n, m, a_i, x \leq 5000k$.

Specifically, the following test cases satisfy additional properties:

• Test case $5$: $a_i = 1$;
• Test case $7$: $a_i = 2$;
• Test case $9$: $a_i = 10$;
• Test case $11$: $a_i \leq 10$;
• Test cases $13, 15$: $\sum a_i \leq 10^6$.

For each test case, you must pass all data that satisfies the constraints and properties of that test case to receive the points for it.