문제
$N$ 행 $M$ 열로 이루어진 2ドル$차원 행렬이 있습니다. 이 행렬의 모든 원소는 처음에 0ドル$입니다.
이 행렬에 다음과 같은 연산을 할 수 있습니다.
- 1ドル$ $r$ $v$
- 1ドル$ 이상 $N$ 이하의 수 $r$과 정수 $v$를 정합니다. $r$번째 행의 모든 원소에 $v$를 더합니다.
- 2ドル$ $c$ $v$
- 1ドル$ 이상 $M$ 이하의 수 $c$와 정수 $v$를 정합니다. $c$번째 열의 모든 원소에 $v$를 더합니다.
이 행렬의 연산을 최소한의 횟수로 진행하여, 주어진 행렬 $A$를 만들고 싶습니다. 만드는 방법을 하나 찾아서 출력하세요.
출력
연산을 유한 번 사용하여 행렬을 $A$로 만들 수 있는 경우, 첫 줄에 행렬을 $A$로 만드는데 필요한 연산 횟수의 최솟값 $Q$를 출력하세요.
다음 $Q$개의 줄의 각 줄에 필요한 연산을 의미하는 세 정수를 공백으로 구분하여 출력하세요. 각 연산은 다음 중 하나여야 합니다.
- 1ドル$ $r$ $v$ $(1 \le r \le N; -10^9 \le v \le 10^9)$
- 2ドル$ $c$ $v$ $(1 \le c \le M; -10^9 \le v \le 10^9)$
불가능한 경우 첫 줄에 $-1$을 출력하세요.
예제 출력 1
3
2 2 1
1 2 2
2 3 -3
W3sicHJvYmxlbV9pZCI6IjI4NDM5IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVkNTg5XHViODJjIFx1YzVmMFx1YzBiMCAoXHVjNWYwXHVjMGIwIFx1Y2MzZVx1YWUzMCkiLCJkZXNjcmlwdGlvbiI6IjxwPiROJCBcdWQ1ODkgJE0kIFx1YzVmNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgJDIkXHVjYzI4XHVjNmQwIFx1ZDU4OVx1YjgyY1x1Yzc3NCBcdWM3ODhcdWMyYjVcdWIyYzhcdWIyZTQuIFx1Yzc3NCBcdWQ1ODlcdWI4MmNcdWM3NTggXHViYWE4XHViNGUwIFx1YzZkMFx1YzE4Y1x1YjI5NCBcdWNjOThcdWM3NGNcdWM1ZDAgJDAkXHVjNzg1XHViMmM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzQgXHVkNTg5XHViODJjXHVjNWQwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVjNWYwXHVjMGIwXHVjNzQ0IFx1ZDU2MCBcdWMyMTggXHVjNzg4XHVjMmI1XHViMmM4XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPiQxJCAkciQgJHYkXHJcblx0PHVsPlxyXG5cdFx0PGxpPiQxJCBcdWM3NzRcdWMwYzEgJE4kIFx1Yzc3NFx1ZDU1OFx1Yzc1OCBcdWMyMTggJHIkXHVhY2ZjIFx1YzgxNVx1YzIxOCAkdiRcdWI5N2MgXHVjODE1XHVkNTY5XHViMmM4XHViMmU0LiAkciRcdWJjODhcdWM5ZjggXHVkNTg5XHVjNzU4IFx1YmFhOFx1YjRlMCBcdWM2ZDBcdWMxOGNcdWM1ZDAgJHYkXHViOTdjIFx1YjM1NFx1ZDU2OVx1YjJjOFx1YjJlNC48XC9saT5cclxuXHQ8XC91bD5cclxuXHQ8XC9saT5cclxuXHQ8bGk+JDIkICRjJCAkdiRcclxuXHQ8dWw+XHJcblx0XHQ8bGk+JDEkIFx1Yzc3NFx1YzBjMSAkTSQgXHVjNzc0XHVkNTU4XHVjNzU4IFx1YzIxOCAkYyRcdWM2NDAgXHVjODE1XHVjMjE4ICR2JFx1Yjk3YyBcdWM4MTVcdWQ1NjlcdWIyYzhcdWIyZTQuICRjJFx1YmM4OFx1YzlmOCBcdWM1ZjRcdWM3NTggXHViYWE4XHViNGUwIFx1YzZkMFx1YzE4Y1x1YzVkMCAkdiRcdWI5N2MgXHViMzU0XHVkNTY5XHViMmM4XHViMmU0LjxcL2xpPlxyXG5cdDxcL3VsPlxyXG5cdDxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1Yzc3NCBcdWQ1ODlcdWI4MmNcdWM3NTggXHVjNWYwXHVjMGIwXHVjNzQ0IDxzcGFuIHN0eWxlPVwiY29sb3I6I2MwMzkyYjtcIj48dT48c3Ryb25nPlx1Y2Q1Y1x1YzE4Y1x1ZDU1YzxcL3N0cm9uZz48XC91PjxcL3NwYW4+XHVjNzU4IFx1ZDY5Zlx1YzIxOFx1Yjg1YyBcdWM5YzRcdWQ1ODlcdWQ1NThcdWM1ZWMsIFx1YzhmY1x1YzViNFx1YzljNCBcdWQ1ODlcdWI4MmMgJEEkXHViOTdjIFx1YjljY1x1YjRlNFx1YWNlMCBcdWMyZjZcdWMyYjVcdWIyYzhcdWIyZTQuIFx1YjljY1x1YjRkY1x1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NDQgXHVkNTU4XHViMDk4IFx1Y2MzZVx1YzU0NFx1YzExYyBcdWNkOWNcdWI4MjVcdWQ1NThcdWMxMzhcdWM2OTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwIFx1ZDU4OVx1YjgyYyAkQSRcdWM3NTggXHVkMDZjXHVhZTMwXHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWI0NTAgXHVjODE1XHVjMjE4ICROJFx1YWNmYyAkTSRcdWM3NzQgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5ZDFcdWIyYzhcdWIyZTQuICQoMSBcXGxlIE4sIE07JCAkTiBcXHRpbWVzIE0gXFxsZSA1MDBcXCwwMDApJDxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgJE4kXHVhYzFjXHVjNzU4IFx1YzkwNFx1Yzc1OCAkaSRcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0ICRBJFx1Yzc1OCAkaSRcdWJjODhcdWM5ZjggXHVkNTg5XHVjNzU4IFx1YzZkMFx1YzE4Y1x1Yjk3YyBcdWM3NThcdWJiZjhcdWQ1NThcdWIyOTQgXHVjODE1XHVjMjE4ICRNJFx1YWMxY1x1YWMwMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzlkMVx1YjJjOFx1YjJlNC4gXHVhYzAxIFx1YzIxOFx1Yzc1OCBcdWM4MDhcdWIzMTNcdWFjMTJcdWM3NDAgJDFcXCwwMDBcXCwwMDAkIFx1Yzc3NFx1ZDU1OFx1Yzc4NVx1YjJjOFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWM1ZjBcdWMwYjBcdWM3NDQgXHVjNzIwXHVkNTVjIFx1YmM4OCBcdWMwYWNcdWM2YTlcdWQ1NThcdWM1ZWMgXHVkNTg5XHViODJjXHVjNzQ0ICRBJFx1Yjg1YyBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjYmRcdWM2YjAsIFx1Y2NhYiBcdWM5MDRcdWM1ZDAgXHVkNTg5XHViODJjXHVjNzQ0ICRBJFx1Yjg1YyBcdWI5Y2NcdWI0ZGNcdWIyOTRcdWIzNzAgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1YzVmMFx1YzBiMCBcdWQ2OWZcdWMyMThcdWM3NTggPHNwYW4gc3R5bGU9XCJjb2xvcjojYzAzOTJiO1wiPjx1PjxzdHJvbmc+XHVjZDVjXHVjMTlmXHVhYzEyPFwvc3Ryb25nPjxcL3U+PFwvc3Bhbj4gJFEkXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YzEzOFx1YzY5NC48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjICRRJFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM3NTggXHVhYzAxIFx1YzkwNFx1YzVkMCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjNWYwXHVjMGIwXHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1OFx1YjI5NCBcdWMxMzggXHVjODE1XHVjMjE4XHViOTdjIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWQ1NThcdWM1ZWMgXHVjZDljXHViODI1XHVkNTU4XHVjMTM4XHVjNjk0LiBcdWFjMDEgXHVjNWYwXHVjMGIwXHVjNzQwIFx1YjJlNFx1Yzc0YyBcdWM5MTEgXHVkNTU4XHViMDk4XHVjNWVjXHVjNTdjIFx1ZDU2OVx1YjJjOFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4kMSQgJHIkICR2JCAkKDEgXFxsZSByIFxcbGUgTjsgLTEwXjkgXFxsZSB2IFxcbGUgMTBeOSkkPFwvbGk+XHJcblx0PGxpPiQyJCAkYyQgJHYkICQoMSBcXGxlIGMgXFxsZSBNOyAtMTBeOSBcXGxlIHYgXFxsZSAxMF45KSQ8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWJkODhcdWFjMDBcdWIyYTVcdWQ1NWMgXHVhY2JkXHVjNmIwIFx1Y2NhYiBcdWM5MDRcdWM1ZDAgJC0xJFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NThcdWMxMzhcdWM2OTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjg0MzkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJNYXRyaXggT3BlcmF0aW9ucyAoRmluZCBPcGVyYXRpb25zKSIsImRlc2NyaXB0aW9uIjoiPHA+VGhlcmUgaXMgYSAyLWRpbWVuc2lvbmFsIG1hdHJpeCBjb25zaXN0aW5nIG9mICROJCByb3dzIGFuZCAkTSQgY29sdW1ucy4gQWxsIGVsZW1lbnRzIG9mIHRoaXMgbWF0cml4IGFyZSBpbml0aWFsbHkgJDAkLjxcL3A+XHJcblxyXG48cD5Zb3UgY2FuIHBlcmZvcm0gdGhlIGZvbGxvd2luZyBvcGVyYXRpb25zIG9uIHRoaXMgbWF0cml4OjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPiQxJCAkciQgJHYkXHJcblx0PHVsPlxyXG5cdFx0PGxpPkNob29zZSBhIG51bWJlciAkciQgZnJvbSAkMSQgdG8gJE4kIGFuZCBhbiBpbnRlZ2VyICR2JC4gQWRkICR2JCB0byBhbGwgZWxlbWVudHMgb2YgdGhlICRyJCYjMzk7dGggcm93LjxcL2xpPlxyXG5cdDxcL3VsPlxyXG5cdDxcL2xpPlxyXG5cdDxsaT4kMiQgJGMkICR2JFxyXG5cdDx1bD5cclxuXHRcdDxsaT5DaG9vc2UgYSBudW1iZXIgJGMkIGZyb20gJDEkIHRvICRNJCBhbmQgYW4gaW50ZWdlciAkdiQuIEFkZCAkdiQgdG8gYWxsIGVsZW1lbnRzIG9mIHRoZSAkYyQmIzM5O3RoIGNvbHVtbi48XC9saT5cclxuXHQ8XC91bD5cclxuXHQ8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5Zb3Ugd2FudCB0byBwZXJmb3JtIG9wZXJhdGlvbnMgb24gdGhpcyBtYXRyaXggYSA8dT48c3Ryb25nPjxzcGFuIHN0eWxlPVwiY29sb3I6I2MwMzkyYjtcIj5taW5pbXVtPFwvc3Bhbj48XC9zdHJvbmc+PFwvdT4gbnVtYmVyIG9mIHRpbWVzIHRvIGNyZWF0ZSBhIGdpdmVuIG1hdHJpeCAkQSQuIEZpbmQgYSBzZXF1ZW5jZSBvZiBvcGVyYXRpb25zIHRvIGRvIHRoaXMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyB0d28gaW50ZWdlcnMsICROJCBhbmQgJE0kLCB3aGljaCByZXByZXNlbnRzIHRoZSBzaXplIG9mIHRoZSBtYXRyaXggJEEkLCBzZXBhcmF0ZWQgYnkgYSBzcGFjZS4gJCgxIFxcbGUgTiwgTTskICROIFxcdGltZXMgTSBcXGxlIDUwMFxcLDAwMCkkPFwvcD5cclxuXHJcbjxwPlRoZSBmb2xsb3dpbmcgJE4kIGxpbmVzIGNvbnRhaW4gJE0kIGludGVnZXIgZWxlbWVudHMgb2YgdGhlICRpJCYjMzk7dGggcm93IG9mICRBJCwgc2VwYXJhdGVkIGJ5IGEgc3BhY2UuIFRoZSBhYnNvbHV0ZSB2YWx1ZSBvZiBlYWNoIG51bWJlciBpcyBhdCBtb3N0ICQxXFwsMDAwXFwsMDAwJC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5JZiB0aGUgbWF0cml4IGNhbiBiZSBtYWRlIGludG8gJEEkIHVzaW5nIGEgZmluaXRlIG51bWJlciBvZiBvcGVyYXRpb25zLCBvdXRwdXQgdGhlJm5ic3A7PHU+PHN0cm9uZz48c3BhbiBzdHlsZT1cImNvbG9yOiNjMDM5MmI7XCI+bWluaW11bTxcL3NwYW4+PFwvc3Ryb25nPjxcL3U+IG51bWJlciBvZiBvcGVyYXRpb25zICRRJCByZXF1aXJlZCB0byBjcmVhdGUgdGhlIG1hdHJpeCAkQSQgaW4gdGhlIGZpcnN0IGxpbmUuPFwvcD5cclxuXHJcbjxwPkluIHRoZSBuZXh0ICRRJCBsaW5lcywgb3V0cHV0IHRocmVlIGludGVnZXJzIHNlcGFyYXRlZCBieSBhIHNwYWNlLCBlYWNoIHJlcHJlc2VudGluZyBhIHJlcXVpcmVkIG9wZXJhdGlvbi4gRWFjaCBvcGVyYXRpb24gbXVzdCBiZSBvbmUgb2YgdGhlIGZvbGxvd2luZzo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4kMSQgJHIkICR2JCAkKDEgXFxsZSByIFxcbGUgTjsgLTEwXjkgXFxsZSB2IFxcbGUgMTBeOSkkPFwvbGk+XHJcblx0PGxpPiQyJCAkYyQgJHYkICQoMSBcXGxlIGMgXFxsZSBNOyAtMTBeOSBcXGxlIHYgXFxsZSAxMF45KSQ8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5JZiBpdCYjMzk7cyBpbXBvc3NpYmxlLCBvdXRwdXQgJC0xJCBpbiB0aGUgZmlyc3QgbGluZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d