Masala E

Xotira 512 MB Vaqt 5000 ms
14

Yozgi lager

Zarif o'z o'quvchilarini yozgi dasturlash lageriga  olib bormoqchi. Zarifning NN ta shogirdi bor, lekin joylar soni atigi KK ta. 

Har bir bolaning uchta asosiy qiziqish darajasi bor:

  • Sport dasturlashga qiziqish darajasi CiC_i
  • Matn terish qobiliyati BiB_i
  • Shaxmatga qiziqish darajasi PiP_i

Har bir o'quvchi (Ci,Bi,Pi)(C_i, B_i, P_i) uchlik qiymatlari bilan ifodalanadi.

Ikki odam orasidagi farq quyidagicha hisoblanadi:

max(CiCj,TiTj,PiPj)\text{max}(|Cᵢ - Cⱼ|, |Tᵢ - Tⱼ|, |Pᵢ - Pⱼ|)

ya’ni, eng katta qiziqish farqi hisobga olinadi.

Zarif KK kishidan iborat jamoa shakllantirmoqchi, lekin u jamoa a’zolari o‘rtasidagi qiziqish darajalaridagi farq iloji boricha kichik bo‘lishini xohlaydi.

Shunday K ta o'quvchini tanlab beringki, ikki o'quvchi orasidagi eng katta farq iloji boricha kamroq bo'lsin.


Kiruvchi ma'lumotlar:

Kirish faylining 1-satrida NN va K(1KN105)K (1 \le K \le N \le 10^5) - umumiy o'quvchilar va lagerda ajratilgan joylar soni kiritiladi.

Keyingi NN ta satrning har birida 3 tadan butun son - Ci,Bi,PiC_i, B_i, P_i qiymatlari beriladi. Bu sonlarning qiymati [0; 255] oralig'ida bo'lishi mumkin.


Chiquvchi ma'lumotlar:

Chiqish faylining birinchi qatorida butun son DD - eng katta farqni chop eting. Keyingi qatorda KK ta butun son - o'quvchining tartib raqamini chop eting. Agar bir nechta yechim mavjud bo'lsa istalganini chop etishingiz mumkin.


Misollar
# input.txt output.txt
1
2 2
1 3 2
2 6 4
3
1 2
2
3 2
3 3 4
1 6 4
1 1 2
2
1 3
3
5 3
6 6 4
6 4 3
3 6 3
4 2 3
5 2 6
3
2 4 5