Dəmir yolu

Цюrix ilə Luqano arasında uzunluğu $s$ kilometr olan dəmir yolu uzanır. Bu dəmir yolu mənzərəli Alp dağlarından keçir, səyahət zamanı təsirli mənzərələr təqdim edir. Bəzi keçidlər dəmir yolu üçün çox yüksək olduğundan, yolda $t$ tunel var. $i$-ci tunel Цюrixdən $a_i$ kilometr məsafədə başlayır və Цюrixdən $b_i$ kilometr məsafədə bitir. (Beləliklə, $i$-ci tunelin uzunluğu $b_i-a_i$-dir.)

Sizin Цюrix ilə Luqano arasında dəmir yolu cədvəliniz var. Цюrixdən Luqanoya $m$ qatar var, $j$-ci qatar $c_j$ dəqiqədə yola düşür. Həmçinin, Luqanodan Цюrixə $n$ qatar var, $k$-ci qatar $d_k$ dəqiqədə yola düşür. Yolda hərəkət edən bütün qatarlar istiqamətindən və tuneldə olub-olmamasından asılı olmayaraq, sabit sürətlə, dəqiqədə 1 kilometr sürətlə hərəkət edir. Marşrutda stansiyalar yoxdur və qatarlar heç vaxt semaforlarda dayanmır. Beləliklə, hər bir qatar təyinat yerinə dəqiq $s$ dəqiqə ərzində çatır.

Qatarın uzunluğu dəmir yolunun uzunluğu ilə müqayisədə əhəmiyyətsizdir, buna görə də bu məsələdə, zəhmət olmasa, hər bir qatarın dəmir yolu boyunca hərəkət edən bir nöqtə olduğunu fərz edin.

Adətən dəmir yolu iki xəttə malikdir: hər istiqamətdə bir xətt. Yeganə istisna tunellərdir. Hər bir tunel yalnız bir xəttə malikdir və bu xətt hər iki istiqamətdə istifadə edilə bilər.

Hər dəfə əks istiqamətlərdə hərəkət edən iki qatar tuneldən kənarda qarşılaşdıqda, onlar təhlükəsiz şəkildə bir-birini keçə bilərlər. Bu, tunelin hər iki ucunda dəqiq qarşılaşan qatarları da əhatə edir. Digər tərəfdən, əgər bir qatar cütü tunelin içərisində dəqiq qarşılaşırsa, toqquşma baş verir.

Tunellərin və qatarların təsvirini nəzərə alaraq, toqquşmanın olub-olmadığını müəyyən edin.

Giriş verilənləri

Birinci sətir dörd tam ədəd $s$, $t$, $m$, $n$ ($1\le s\le 1000000000$, $0\le t\le 100000$, $0\le m,n\le 2000$) — dəmir yolunun uzunluğu, tunellərin sayı, Цюrixdən qatarların sayı və Luqanodan qatarların sayı.

İkinci sətir $t$ tam ədəd $a_i$ ($0\le a_i<s$) — tunellərin başlanğıc mövqelərini ehtiva edir.

Üçüncü sətir $t$ tam ədəd $b_i$ ($0<b_i\le s$) — tunellərin son mövqelərini ehtiva edir.

Hər bir $i$ üçün $1$-dən $t$-ə qədər, $a_i<b_i$ şərti yerinə yetirilir. Həmçinin hər bir $i$ üçün $1$-dən $t-1$-ə qədər, $b_i<a_{i+1}$ şərti yerinə yetirilir. (Başqa sözlə, hər bir tunelin müsbət uzunluğu var, tunellər kəsişmir, tunellər Цюrixdən məsafənin artma sırasına görə verilmişdir.)

Dördüncü sətir $m$ tam ədəd $c_j$ ($0\le c_j\le 1000000000$) — Цюrixdən yola düşən qatarların başlanğıc vaxtını (dəqiqə ilə) ehtiva edir. Onlar artma sırasına görə verilir, yəni $c_j<c_{j+1}$ bütün uyğun $j$ üçün.

Beşinci sətir $n$ tam ədəd $d_k$ ($0\le d_k\le 1000000000$) — Luqanodan yola düşən qatarların başlanğıc vaxtını (dəqiqə ilə) ehtiva edir. Onlar artma sırasına görə verilir, yəni $d_k<d_{k+1}$ bütün uyğun $k$ üçün.

Çıxış verilənləri

Ən azı bir toqquşma baş verərsə, "YES" (dırnaqsız) çıxarın, əks halda "NO" çıxarın.

Nümunələr

Qeyd

Birinci nümunədə Цюrixdən 100 kilometr uzunluğunda yolda iki tunel var: biri Цюrixdən 20-dən 30 kilometrə qədər, digəri Цюrixdən 50-dən 60 kilometrə qədər. Цюrixdən gələn yeganə qatar Luqanoya gedən bütün qatarları aşağıdakı kimi qarşısını alır:

• birinci Цюrixdən 5 kilometr məsafədə qarşılaşır,

• ikinci tunellər arasında yarı yolda qarşılaşır,

• üçüncü Luqanodan 10 kilometr məsafədə qarşılaşır,

• dördüncü Цюrixdən gələn qatar təyinat yerinə çatdıqdan çox sonra başlayır.

İkinci nümunədə iki qatar yeganə tunelin ortasında dəqiq qarşılaşır və nəticədə qəza baş verir.

Üçüncü nümunədə iki qatar Цюrixə daha yaxın olan tunelin sonunda dəqiq qarşılaşır. Dördüncü nümunədə onlar tunelin digər ucunda dəqiq qarşılaşır. Hər iki hal təhlükəsizdir, çünki qatarlar bir-birini keçərək təhlükəsiz şəkildə təyinat yerinə çatır.

Qiymətləndirmə

Son blokdan başqa bütün bloklarda $s$, bütün $c_j$ və bütün $d_k$ cütdür.

Blok 1 (14 bal): $t,m,n\le 100$ və $s\le 5000$.

Blok 2 (16 bal): $t\le 5000$ və $s\le 1000000$.

Blok 3 (41 bal): əlavə məhdudiyyətlər yoxdur.

Blok 4 (29 bal): əlavə məhdudiyyətlər yoxdur. Həmçinin, $s$, $c_j$ və $d_k$ mütləq cüt deyil.