There are three machines on the new toy factory: A, B and C. The factory makes toys by processing each toy on these machines in order A, B, C. Your task is to create N toys as soon as possible. You know the time to process each toy on each machine: a_i, b_i and c_i. You can select an arbitrary order of processing toys. The second machine is so fast that at least one of the following two statements holds: max(b_i) ≤ min(a_i) or max(b_i) ≤ min(c_i).

The first line of the input contains the number of toys N (1 ≤ N ≤ 10⁵). The next N lines contain three integers each: a_i, b_i and c_i (1 ≤ a_i, b_i, c_i ≤ 10⁶).

Output the minimal possible processing time on the first line. The second line must contain an example of optimal processing order — a permutation of toy numbers from 1 to N.