Віталій полюбляє грати в азартні ігри. У його улюблену гру грає n людей. Гравці пронумеровані від 1 до n. У кожного гравця є два баланси: перший — його виграш, другий — нагорода за його голову. Спочатку у кожного гравця виграш — 0, а нагорода за голову — 1. У грі відбувається рівно n−1 послідовних подій такого виду: береться два різні гравці, які ще не вибули з гри, і перший з них вибиває другого. У результаті цієї операції до виграшу першого додається нагорода за голову другого, а до нагороди за голову першого додається половина нагороди за голову другого. Другий гравець вибуває з гри, тобто він вже не може нікого вибивати та бути знову вибитим кимось. Вам потрібно знайти послідовність подій, таких, щоб сумарний виграш усіх гравців був мінімально (або максимально) можливий. Входные данныеПерший рядок містить два цілі числа n та t (2≤n≤10 5,0≤t≤1) — кількість гравців та число, яке вказує для мінімального чи максимального виграшу ви розв'язуєте задачу. Число 0 відповідає задачі для мінімального виграшу, 1 — для максимального. Выходные данныеВиведіть n−1 рядків. В i-ому рядку повинно бути два цілі числа a i​ та b i​ (1≤a i​ ,b i​ ≤n), це означає, що гравець під номером a i​ вибив гравця b i​ на кроці i. ПримечаниеРозберемо перший приклад. Баланси гравців на кожному кроці:Баланси на початку: (0,1),(0,1),(0,1). Баланси після першого кроку: (0,1),(1,1. 5),(0,1). Баланси після другого кроку: (0,1),(2,2),(0,1). Сумарний виграш гравців: 2+0+0=2Розберемо другий приклад. Баланси гравців на кожному кроці:Баланси на початку: (0,1),(0,1),(0,1). Баланси після першого кроку: (0,1),(0,1),(1,1. 5). Баланси після другого кроку: (0,1),(1. 5,1. 75),(1,1. 5). Сумарний виграш гравців: 1+0+1. 5=2. 5ОцениваниеУ 50% тестів t=0. У інших 50% тестів t=1. timerЛимит на использование времени: 1000 msstorageЛимит на использование памяти: 256 MBarrow_circle_upУ вас есть еще 50 попыток отправить эту задачуПримерыНиже вы найдете примеры входных данных и ответы которые должна вывести ваша программа. Пример ввода #13 0Пример ответа #12 32 1Пример ввода #23 1Пример ответа #23 12 3