Inverse Fenwick tree

Limits: 3 sec., 512 MiB

This statement was translated automatically from Ukrainian.

Zenyk is interested in how to solve problems using a Fenwick tree with range maximum queries. To do this, he is solving the following problem.

You are given an array \(a\) of \(n\) elements, initially filled with zeros. You need to process a sequence of queries, each of which is of one of two types:

1. Given \(x\) and \(y\), update \(a[x]\) to \(\max(a[x], y)\);

2. Given \(p\), find the maximum value on the prefix \([1, p]\), i.e., \(\max(a_1, a_2, \dots, a_p)\).

Zenyk solved the problem and left data about the queries of the second type – for each query, the prefix \(p\) and the maximum value \(v\) on this prefix are known. All these results are known in the correct chronological order. Marichka saw these results and wondered what the minimum number of type-one queries Zenyk could have made.

Input

The first line contains 2 integers \(k\) and \(n\) – the number of queries of the second type and the length of the array.

The next \(k\) lines contain 2 integers \(p\) and \(v\) each – it is known that the maximum value on the prefix \([1, p]\) was equal to \(v\).

Output

In the first line, print the minimum number of type-one queries that Zenyk could have performed. If Zenyk made a mistake and the query results are impossible, print -1.

If the answer exists, in the following lines print a possible sequence of type-one queries. In each line, print 3 integers \(c\), \(x\), \(y\), where \(c\) – how many queries of the second type occurred before this query of the first type, and the query changes \(a[x]\) to \(\max(a[x], y)\).

It must hold that \(0 \le c \le k\), \(1 \le x \le n\), \(1 \le y \le 10^6\).

The queries can be printed in any order. If there are multiple sequences of queries, print any of them.

Constraints

\(1 \le k \le 2 \cdot 10^5\),

\(1 \le n \le 10^6\),

\(1 \le p_i \le n\),

\(1 \le v_i \le 10^6\).

Samples

Input (stdin) сopy	Output (stdout) сopy
4 7 4 7 4 10 3 7 6 47	3 0 5 47 0 2 7 1 4 10

Input (stdin) сopy	Output (stdout) сopy
2 1 1 7 1 4	-1

Notes

In the first example, it is possible to first set 47 at position 5 and 7 at position 2, the array becomes [0, 7, 0, 0, 47, 0, 0].

After this, we execute a query of the second type and on the prefix of length 4 the maximum value is 7. After this, we set the value at position 4 to 10 and perform the remaining queries of the second type, getting the correct result for each of them.

In the second example, the value at the first position must first be 7, and then 4, which is impossible since we cannot decrease values.