Masala F

Tasavvur qiling, “Chigirtkalar Ligasi” bo‘lib o‘tmoqda. Uzunligi $m$ birlik bo‘lgan aylana ustida bir nechta chigirtka poygada qatnashmoqda. Har bir chigirtka bir xil tezlikga ega, har sekundda 1 birlik masofa bosib o‘tadi. Lekin ularning xarakteri o‘zgacha: dastlab ba’zilari harakatni chap (L), ba’zilari esa harakatni o‘ng (R) yo'nalishda sakrash bilan boshlaydi.

Aylana ustida $n$ ta chigirtka joylashgan bo‘lib, ularning har biri poyga boshida $s_i$ pozitsiyada turibdi va $d_i \in [L, R]$ yo'nalishda bir vaqtda barcha chigirtka harakatni boshlaydi. Pozitsiyalar soat strelkasiga qarama-qarshi yo‘nalishda $1$ dan $m$ gacha raqamlangan.

Biroq bu oddiy poyga emas! Aylana ustida maxsus qoidalar amal qiladi:

1. Agar ikki chigirtka to‘qnashib ketsa, ular birdaniga yo‘nalishlarini teskari tomonga o‘zgartiradi (etibor bering chigirtkalar vaqt birligining yarmi uchun qandaydir yo'nalishda va vaqt birligining yana yarmi uchun teskari yo'nalishda harakatlanishi mumkin).
2. Agar bir vaqtning o‘zida bir nechta to‘qnashuvlar yuz bersa, barchasi bir vaqtda o'z yo'nalishini qarama-qarshisiga o'zgartiradi.
3. Harakat davomida chigirtka $1$ pozitsiyadan o‘tganda $m$ pozitsiyaga qaytadi, va aksincha.

Sizning vazifangiz poyga $t$ birlik vaqt o‘tgach, har bir chigirtkaning yakuniy pozitsiyasini aniqlang.

Kirish faylining dastlabki satrida $n,m,t(2\leq n\leq 3*10^5,2\leq m\leq 10^9,0\leq t\leq 10^{18})$ - mos ravishda chigirtkalar soni, doira uzunligi va vaqt birligi.

Kiyingi $n$ ta satrda $s_i,d_i(1\leq s_i \leq m, d_i\in [L,R])$ mos ravishda $i-$chigirtka joylashgan pozitsiya va chigirtka yo'nalishi. $L$ va $R$ mos ravishda soat yo'nalishi bo'yicha va soat miliga teskari yo'nalishga mos keladi. 

Chiqish faylida $t$ vaqt birligidan so'ng, dastlabki chigirtkadan boshlab oxirgi chigirtkagacha barcha pozitsiyalarni bitta satrda probil bilan ajratilgan holda chop eting.