Masala #0177

Shermatning tug’ilgan kunida unga avtobus uchun chiptalar sovg’a qilishdi. Shermat boshida ozroq xafa bo’lgandi, lekin chiptalar oddiy emas balki super chiptalar ekanligini ko’rganidan keyin ancha taskin topdi.

Hozirda uning qo’lida \(m\) ta chipta bor va chiptalar 3 xil turga bo’linadi:
1. Bu chipta orqali \(a\) bekatdan \(b\) bekatgacha borsa bo’ladi.
2. Bu chipta orqali \(a\) bekatdan \([l,r]\) oraliqdagi ixtiyoriy bekatga borsa bo’ladi.
3. Bu chipta orqali esa \([l,r]\) oraliqdagi ixtiyoriy bekatdan \(a\) bekatga borsa bo’ladi.

Har bir chipta uchun avtobus qancha vaqt harakatlanishi ko’rsatilgan. Bekatlar soni jami \(n\) ta bo’lib, dastlab Shermat \(s\) - bekatda turibdi. Shermat \(s\) - bekatdan qolgan bekatlarga eng kamida qancha vaqt sarflab yetib olish mumkinligiga qiziqmoqda. Shaharda avtobus reyslari shunchalik ko’pki bekatdan bir avtobusdan tushib boshqasiga o’tirishga ketgan vaqtni 0 deb hisoblash mumkin.

Birinchi qatorda 3 ta butun son - \(n\), \(m\), va \(s\) – bekatlar soni, chiptalar soni va Shermat turgan bekat beriladi \((1 ≤ n, m ≤ 10^5, 1 ≤ s ≤ n)\). Keyingi \(m\) ta qatorda chiptalar tavsifi kiritiladi va ular quyidagicha ifodalanadi:

• \(1 \space a \space b \space t\) - bu birinchi turli chipta bo'lib, bu chipta orqali \(a\) bekatdan \(b\) bekatga \(t\) vaqtda borish mumkin.
• \(2 \space a \space l \space r \space t\) - bu ikkinchi turli chipta bo'lib, bu chipta orqali \(a\) bekatdan \([l, r]\) oraliqdagi ixtiyoriy bekatga \(t\) vaqtda borish mumkin.
• \(3 \space a \space l \space r \space t\) - bu uchinchi turli chipta bo'lib, bu chipta orqali \([l, r]\) oraliqdagi ixtiyoriy bekatdan \(a\) bekatga \(t\) vaqtda borish mumkin.

Yagona qatorda probel bilan ajratilgan \(n\) ta sonni chiqaring, \(i\) - son \(s\) bekatdan \(i\) - bekatgacha borish mumkin bo'lgan eng qisqa vaqtga teng bo'lsin, agar borishni iloji yo'q bo'lsa \(-1\) chiqaring.