E. Төгсгөлгүй матриц

хугацааны хязгаарлалт 3 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Оросын сансарт аялагч Алиса Селезнева бусад 21-р зууны сүүл үеийн охид нартай адилаар шинжлэх ухаанд дуртай нэгэн юм. Тэрээр саяхан MIT (Moscow Institute of Time)-д зочилсон ба тэнд тус сургуулийн захирал болон цаг хугацааны машиныг зохион бүтээгч, эрдэмтэн Петров нар түүнд уг цаг хугацааны машины бүтцийн талаар хэлж өгчээ.

Цаг хугацааны машины танилцуулгын үеэр Алиса уг машин нь өндөр хурдгүй болохыг анзаарсан бөгөөд охин уг сул талын шалтгаанд нь нэг их анхаарал хандуулсангүй. Гэнэтхэн тэд уг машинд нарийвчилсан шалгалт хийхээр болсон ба уг цаг хугацааны машины шийдэгдсэн байх ёстой нэг асуудал нь оновчтой алгоритмын дагуу шийдэгдээгүй болохыг олж мэджээ. Хэрэв та уг асуудлыг оновчтой шийдэх арга олбол уг цаг хугацааны машин нь илүү хурдан бөгөөд бага эрчим хүчээр ажиллах юм.

Ажилчдын нэг нь ч шийдэж чадаагүй уг асуудал нь дараах байдалтай байв. $a$ матриц оршин байх бөгөөд уг матриц нь дараах дүрмийг хангасан байна:

Нүднүүд нь нэгээс эхлэх дараалсан эерэг бүхэл тоонууд байна. Түүнчлэн хэрэв

  1. $max(i, j) < max(t, k)$;
  2. $max(i, j) = max(t, k)$ бөгөөд $j < k$;
  3. $max(i, j) = max(t, k)$, $j = k$ бөгөөд $i > t$

байвал $a_{i, j} < a_{t, k}$ ($i, j, t, k ≥ 1$) байна.

Ийм байдлаар эхний $36$ тоог байрлуулсны дараа $a$ матриц нь дараах байдалтай харагдана:

Асуудлыг шийдэхийн тулд та $x_{1}, y_{1}, x_{2}$ болон $y_{2}$ ($x_{1} ≤ x_{2}, y_{1} ≤ y_{2}$)-ын утга өгөгдсөн байхад маш хурднаар илэрхийллийн утгыг олох хэрэгтэй юм.

Уг илэрхийллийн утга нь хангалттай том байх тул уг тооны сүүлийн $10$ цифрийг мэдэж байхад хангалттай.

MTI-дахь хэн ч өгөгдсөн асуудлыг шийдэж чадахгүй байв. Алиса цаг хугацааны машиныг ашиглан өнгөрсөнд очиж танд туслах юм.

Таны даалгавар бол $x_{1}, y_{1}, x_{2}$ болон $y_{2}$-ын өгөгдсөн утгуудыг ашиглан өгөгдсөн илэрхийллийн сүүлийн $10$ цифрийг олох программ бичих юм.

Оролт

Эхний мөрөнд та уг асуудлыг шийдэхийн тулд шалгах ёстой тестүүдийн тоо болох бүхэл тоо $t$ ($1 ≤ t ≤ 10^{5}$) өгөгдөнө.

Дараагийн $t$ мөрийн мөр болгонд нэг тестийг илэрхийлэх 4 бүхэл тоо $x_{1}, y_{1}, x_{2}$ болон $y_{2}$ ($1 ≤ x_{1} ≤ x_{2} ≤ 10^{9}, 1 ≤ y_{1} ≤ y_{2} ≤ 10^{9}$) зайгаар тусгаарлагдан өгөгдөнө.

Гаралт

Тест бүрийн хувьд хэрэв уг илэрхийлэл нь хамгийн ихдээ $10$ цифр агуулж байвал уг илэрхийллийн утгыг хэвлэнэ. Бусад тохиолдолд эхлээд 3-н ширхэг "$.$" (хашилтгүйгээр) тэмдэгт хэвлэх ба араас нь уг илэрхийллийн сүүлийн 10 цифрийг хэвлэнэ. Тест болгоны хариултыг дан мөрөнд хэвлэнэ үү. Жишээнд өгөгдсөн хэлбэрийг аль болох нарийвчлан дагана уу.

Орчуулсан: Баатархүү

Жишээ тэстүүд

Оролт
5
1 1 1 1
2 2 3 3
2 3 5 6
100 87 288 2002
4 2 5 4
Гаралт
1
24
300
...5679392764
111
Сэтгэгдлүүдийг ачааллаж байна...