B. Онлайн чат

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

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

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

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

Бяцхан X ба Z бол сайн найзууд юм. Тэд үргэлж онлайнд чаталдаг хэдий ч аль аль нь цагийн хуваарьтай байдаг.

Бяцхан Z тогтмол цагийн хуваарьтай. Тэр $a_{1}$-ээс $b_{1}$, $a_{2}$-с $b_{2}$, ..., $a_{p}$-с $b_{p}$(хилийг оролцуулна) цагуудын хооронд онлайнд байдаг. Харин бяцхан X-ийн цагийн хуваарь их хачирхалтай ба тэр хэдэн цагаас босохоос шалтгаална. Хэрэв тэр $0$ цагт босвол $c_{1}$-с $d_{1}$, $c_{2}$-с $d_{2}$, ..., $c_{q}$-с $d_{q}$ (хилийг оролцуулна) цагуудын хооронд онлайн байна. Гэвч хэрвээ тэр $t$ цагт босвол эдгээр сегментүүд нь $t$-р шилжиж $[c_{i} + t, d_{i} + t]$ (бүх $i$-үүд) болно.

Хэрвээ X ба Z хоёулаа зэрэг онлайн байгаа бол тэд баяртайгаар чатлах болно. Бидний мэдэж байгаачлан бяцхан X $l$-с $r$-ийн (хилийг оролцуулна) хоорондох бүхэл цагт босож чадна. Мөн X нь Z-тэй чатлах тохиромжтой цагт босохыг хүсдэг (Тэдний цагийн хуваарьт хамт байх цаг дор хаяж нэг байх ёстой). $[l, r]$ сегментэд тэд хамт байх хэдэн цаг байгаа вэ?

Оролт

Эхний мөрөнд зайгаар тусгаарласан дөрвөн бүхэл тоо $p, q, l, r$ ($1 ≤  p, q ≤ 50; 0 ≤ l ≤ r ≤ 1000$) байна.

Дараагийн $p$ мөр бүр зайгаар тусгаарлагдсан хоёр бүхэл тоо $a_{i}, b_{i}$ ($0 ≤ a_{i} < b_{i} ≤ 1000$) байна. Дараагийн $q$ мөр бүр зайгаар тусгаарлагдсан хоёр бүхэл тоо $c_{j}, d_{j}$ ($0 ≤ c_{j} < d_{j} ≤ 1000$) байна.

Бүх $i$ ба $j$-ийн хувьд $b_{i} < a_{i + 1}$ мөн $d_{j} < c_{j + 1}$ нь үнэн байна.

Гаралт

Нэг бүхэл тоо хэвлэнэ. $[l, r]$ сегментэд онлайнд ярилцахад тохиромжтой цагийг хэвлэнэ.

Орчуулсан: Даариймаа

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

Оролт
1 1 0 4
2 3
0 1
Гаралт
3
Оролт
2 3 0 20
15 17
23 26
1 4
7 11
15 17
Гаралт
20
Сэтгэгдлүүдийг ачааллаж байна...