Спорттық бағдарламалау федерациясы өз фитнес-залын ашқалы жатыр. Сіз — қабылдау орнында қызмет ететін әкімшісіз, және киім ауыстыратын бөлмедегі шкафтардың кілтін үлестіру — сіздің міндетіңіз.

1. Ертең залға \(m\) жаттығушы келеді, оларды \(1\)-ден \(m\)-ге дейін нөмірлейік.

2. Залда барлығы \(k\) шкаф бар, бірақ соның тек \(n\)-і ғана жарамды (\(n \le k\)). Сізге осы жарамды \(n\) шкафтың нөмірлері белгілі.

3. Күн бойы \(2m\) оқиға болады: әрбір қонақ бір рет келеді және бір рет кетеді. Оқиғалардың реті \(a_1,a_2,\dots,a_{2m}\) массиві арқылы берілген, мұндағы \(a_t\) — \(t\) сәтінде залға келген немесе кеткен жаттығушының нөмірі. Әрбір қонақ (\(1 \le i \le m\)) бұл тізімде дәл екі рет кездеседі: біріншісі — келген кезі, екіншісі — кеткен кезі.

Жаттығушы алғаш келген кезде, сіз оған бір жарамды шкафты тағайындап, кілтін бересіз. Қонақ залда жүрген уақытта сол шкафты пайдаланады; кетерінде кілтін тапсырады, және шкаф қайта босайды.

\(A_t\) — \(t\) сәтінде залда жүрген келушілердің жиынтығы делік (\(0 \le |A_t| \le m\)). Тек \(|A_t| \ge 2\) болған сәттер ғана қарастырайық (мұндай сәттің кемінде біреуі болатынына кепілдік берілген). Әрбір осындай \(t\) үшін шкафтар арасындағы ең аз арақашықтықты: \[D_t := \min_{i \ne j;; i,j \in A_t} |x_i - x_j|,\] деп анықтайық. Мұндағы \(x_p\) — \(p\) келушіге тиесілі шкафтың нөмірі.

Киім ауыстыратын бөлменің кеңдігі деп: \[D := \min_{\substack{t:;|A_t|\ge 2}} D_t,\] яғни \(D_t\)-ның тәулік ішіндегі ең төмен мәнің алайық. Сіздің мақсатыңыз — шкафтарды қонақтарға киім ауыстыратын бөлменің кеңдігі мүмкіндігінше үлкен болатындай етіп тағайындау.

Енгізу

Бірінші жолда үш бүтін сан \(n\), \(m\), \(k\) берілген: (\(1 \le n \le 10^6\), \(1 \le m \le n\), \(n \le k \le 10^9\))

Екінші жолда \(n\) әртүрлі бүтін сан — \(x_1, x_2, \dots, x_n\) берілген, мұндағы әр \(x_i\) (\(1 \le x_i \le k\)) — жұмыс істеп тұрған шкафтардың нөмірі.

Үшінші жолда \(2m\) бүтін сан — \(a_1, a_2, \dots, a_{2m}\) берілген, мұндағы әр сан (\(1 \le a_t \le m\)) \(1\)-ден \(m\)-ге дейінгі келушіні білдіреді. Әрбір келуші бұл тізімде тура екі рет кездеседі: келгенде бір рет және кеткенде бір рет.

Шығару

\(m\) бүтін санды, \(1\)-ден \(m\)-ге дейінгі жаттығушыларына тағайындалатын шкафтардың нөмірлерін шығарыңыз. Егер оптималды үлестірімдердің бірнешеуі бар болса, олардың кез келгенін шығаруға болады.

Мысалдар

Енгізу 1

6 3 8
7 1 5 8 6 2
1 1 3 2 3 2

Жауап 1

8 1 8

Енгізу 2

11 6 11
10 3 8 4 2 1 7 5 6 9 11
2 6 5 3 2 1 1 4 5 3 4 6

Жауап 2

10 11 1 11 4 7