Crystals

All submissions for this problem are available.

The Evil Magician of Byteland was performing evil magical experiments, and he has left you with an impressive collection of evil magical crystals which he produced. Honestly, you would be overjoyed to dispose of (or in other words: destroy) these crystals, but destroying a magical crystal is not so easy. To achieve thus, you need to connect three different crystals (red, green and blue) and cast some magic spell to destroy this particular triplet. Each magical crystal has its own mana level. You need a certain amount of your own mana to destroy the triplet, precisely equal to the product of the mana levels of the crystals in the triplet you are destroying. Fortunately, your crystals are all already grouped in triplets, and there are no leftovers (so it is possible to actually destroy all of them); unfortunately, the composition of the triplets is not necessarily optimal from the point of view of mana consumption. However, you are allowed to choose two crystals of the same color, and swap them within triplets (crystals become very unstable and hazardous when not part of a triplet, so you cannot perform any operations more complicated than swapping). But there is a catch (there always is, isn't there?): swapping crystals requires a magic spell -- a spell with a significant mana cost, and what makes matters worse, using this spell (as any other spell) on the crystals being swapped makes them accumulate more mana into their mana level (exactly by 1). Try to minimize the amount of mana you need to use to destroy all the crystals!

Input

First, 2 ≤ n ≤ 10⁵, the number of crystals of each color. Then, 0 ≤ c ≤ 10⁴, the mana cost of the swapping spell. After that, n triplets of integers follow, the ith triplet consisting of 0 ≤ r_i ≤ 100, 0 ≤ g_i ≤ 100, 0 ≤ b_i ≤ 100, representing the initial mana levels of successive Red, Green and Blue crystals, respectively.

Output

First 0 ≤ t ≤ 10⁶, the number of swaps. Then, t descriptions of the swaps in the order in which they are applied, each of the form: 1≤p≤3, 1≤x≤n, 1≤y≤n, meaning a swap between crystals of the xth and yth triplets (p=1 stands for Red, 2 for Green, 3 for Blue).

Example

Input:
3 10
1 1 1
5 5 5
10 10 10

Output:
2
1 1 3
3 1 2
Score:
11*1*6 + 5*5*2 + 2*10*10 + 10 + 10 = 336

---

Date:	2009-07-10
Time limit:	1s
Source limit:	50000B
Languages:	All except: TCL PERL6 CLOJ GO PYTH 3.1.2 F# C++ 4.3.2 ERL