Masala #1205

Xotira 256 MB Vaqt 2000 ms
14

Maxsus sovg'a

Qorbobo sizga juda injiq bola uchun sovg'a tayyorlashni buyurdi. Bola sovg'a sifatida ko'pi bilan \(N\) ta shar olishni xohlaydi, lekin u injiqligi tufayli hamma sharlari och rangli bo'lib qolishini xohlamaydi, xuddi shunday to'q rangli bo'lib qolishini ham xohlamaydi. Sizga Qorbobo \(K\) xil rangdagi sharlarning har biridan cheksiz miqdorda ishlatishga ruxsat berdi. Siz sovg'a bolaga yoqishi uchun quyidagicha usulda sovg'ani tayyorlashingiz kerak:

  • \(K\) xil shardan 1 tadan \(N\) tagacha qilib yasash mumkin bo'lgan barcha turli sharlar to'plamini yasab chiqasiz va ularni och ranglardan to'qga qarab saralaysiz. (Leksikografik saralashga o'xshash, aniqroq tushunish uchun namunaviy test va uning izohini tekshiring)
  • Tasavvur qiling sizda \(S\) ta sovg'a (sharlar to'plami) hosil bo'ldi. Siz bolaga sovg'a sifatida \(\frac{S}{2}\) - sovg'ani berasiz, chunki bu sovg'a ranglar jihatidan muvozanatlangan bo'ladi.

Bolaga berilgan sovg'adagi sharlar ranglarini chiqaring.

E'tibor bering: To'plamda bir nechta bir xil rangdagi sharlar bo'lishi mumkin.


Kiruvchi ma'lumotlar:

\(N\) va \(K\) natural sonlari: \(1 \leq N, K \leq 3*10^5\)


Chiquvchi ma'lumotlar:

Masala javobini chiqarishda ranglarni sonlar bilan ifodalang. Bunda 1 soni eng och rangga, \(K\) soni eng to'q rangga mos keladi.


Misollar
# input.txt output.txt
1
2 2
1 2
2
2 3
2 1
Izoh:

1-test uchun izoh:

Yasash mumkin bo'lgan to'plamlar: (1), (1,1), (1,2), (2), (2,1), (2,2)

6/2=3 - eng kichik to'plam (1,2).