Розбиття на пари
Космічні археологи виявили на планеті в сусідній зоряній системі n древніх артефактів, які вони пронумерували від 1 до n. Кожен артефакт має k різних параметрів, кожен з яких представлений цілим числом. Артефакт i має параметри a[i,1], a[i,2], ..., a[i,k]. Виявилося, що перші параметри у всіх артефактів різні: для всіх i ≠ j виконується a[i,1] ≠ a[j,1], при цьому інші параметри у артефактів можуть збігатися.
Вчені також виявили текст, згідно з яким для активації артефактів їх необхідно особливим чином розбити на пари і поєднати. Розбиття артефактів на пари є коректним, якщо для кожного t від 1 до k можна вибрати таке число b[t], що воно лежить на відрізку між значеннями t-го параметра артефактів кожної пари. Тобто, якщо артефакти i і j утворюють пару, має виконуватися умова a[i,t] ≤ b[t] ≤ a[j,t] або умова a[i,t] ≥ b[t] ≥ a[j,t].
Тепер вчені хочуть з'ясувати, чи правильно розшифровано текст. Для цього необхідно перевірити, чи існує коректне розбиття артефактів на пари. Кожен артефакт повинен увійти рівно в одну пару в розбитті.
Напишіть програму, яка за описом параметрів артефактів визначає, чи можна розбити їх на пари таким чином, щоб для кожного параметра існувало значення, що лежить між значеннями цього параметра артефактів кожної пари, і в разі позитивної відповіді виводить таке розбиття.
Вхідні дані
У першому рядку задано цілі числа n і k (2 ≤ n ≤ 2 * 10^5, n парне, 1 ≤ k ≤ 7) - кількість артефактів і кількість параметрів. У наступних n рядках задано по k цілих чисел a[i,1], a[i,2], ..., a[i,k] - параметри артефактів (-10^9 ≤ a[i,j] ≤ 10^9, всі значення a[i,1] різні).
Вихідні дані
Виведіть "NO", якщо потрібного розбиття на пари не існує.
В іншому випадку виведіть "YES" у першому рядку. Далі виведіть n / 2 рядків, у кожному рядку виведіть по два числа - номери артефактів, з яких слід скласти пару. Кожен артефакт повинен бути виведений рівно один раз.
Якщо існує декілька коректних розбиттів артефактів на пари, дозволяється вивести будь-яке з них.