你在一家工厂工作，负责操作一台切纸机。这台机器可以将任意长度的纸条切成 $2$ 等份或 $3$ 等份。

作为日常工作的一部分，你会收到一条长度为 $n$ 的纸条，以及一份你应当制作的目标纸条长度列表。该列表由 $m$ 对整数 $c_i$ 和 $l_i$ 组成，意味着你的工作结果应该恰好包含 $c_i$ 条长度为 $l_i$ 的纸条。时局艰难，你的客户都不容忍任何纸张损耗，因此所有纸条的总长度等于 $n$，即 $\sum_{i=1}^{m} l_i \cdot c_i = n$。

确定是否可能完成该订单，并设计一份操作说明列表来实现这一目标。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 2^{62}$) —— 你在开始时获得的纸条长度。保证对于某些整数 $a$ 和 $b$，有 $n = 2^a \cdot 3^b$。

第二行包含一个整数 $m$ ($1 \le m \le 700$) —— 描述最终长度的对数。

接下来的 $m$ 行，第 $i$ 行包含两个整数 $l_i$ 和 $c_i$ ($1 \le l_i \le n, 1 \le c_i \le n$)。保证所有的 $l_i$ 互不相同，且所有纸条的总长度等于 $n$。

输出格式

如果无法完成订单，在输出的唯一一行中打印 "NO"（不含引号）。

否则，在输出的第一行打印 "YES"（不含引号）。在第二行打印操作块的数量 $k$ ($0 \le k \le 500\,000$)。接下来打印 $k$ 行，包含操作块的描述。每个描述由三个整数 $l_i$、$c_i$ 和 $o_i$ ($1 \le l_i, c_i \le n, 2 \le o_i \le 3$) 组成，表示应当使用切纸机将 $c_i$ 条长度为 $l_i$ 的纸条中的每一条切成 $o_i$ 等份。

保证如果存在解，则存在一个使用不超过 $500\,000$ 个操作块的解。

如果存在多个可能的解，你可以输出其中任意一个。

样例

输入样例 1

1
1
1 1

输出样例 1

YES
0

输入样例 2

6
2
2 2
1 2

输出样例 2

YES
2
6 1 3
2 1 2

输入样例 3

6
3
2 1
3 1
1 1

输出样例 3

NO

输入样例 4

6
2
5 1
1 1

输出样例 4

NO

说明

在第二个样例中，不能交换操作块的顺序。