7232번 - Robotai 서브태스크다국어

Robotų konstruotojas Daumilas sukonstravo M robotų, kuriuos nori išbandyti apskritimo formos arenoje. Arena padalinta į N sekcijų, iš eilės sunumeruotų nuo 1 iki N pagal laikrodžio rodyklę: i-toji (1 ≤ i ≤ N − 1) sekcija ribojasi su i + 1- ąja, o N-toji sekcija papildomai ribojasi su 1-ąja sekcija.

Daumilas gali kiekvieną arenos sekciją arba palikti tuščią, arba joje pastatyti robotą arba sieną (bet ne abu). Kiekvienam robotui Daumilas įveda komandą: i-tajam robotui įvedama komanda a_i. Tada visi robotai vienu metu pradeda simuliaciją. i-tasis robotas a_i sekundžių juda pastoviu 1 sekcijos per sekundę greičiu pagal laikrodžio rodyklę. Jeigu roboto kelyje pasitaiko nejudančių robotų, jis juos stumia tolyn nesulėtindamas greičio. Robotas anksčiau komandos (t. y. nepraėjus visoms a_i sekundžių) laiko sustoja tik tada, kai jis arba jo stumiamas robotas atsiremia į sieną. Atkreipkite dėmesį, kad vienoje sekcijoje telpa tik vienas robotas, o robotams prasilenkti neįmanoma.

Daumilas nori patikrinti, ar jo robotai veikia teisingai ir jam reikia žinoti, kokiose galutinėse sekcijose robotai turėtų atsidurti. Jo programavimo įgūdžiai nėra patys geriausi, todėl jis norėtų paprašyti jūsų pagalbos.

Suskaičiuokite, kokiose sekcijose robotai atsidurs simuliacijai pasibaigus.

Pirmoje eilutėje duoti sveikieji skaičiai N – apskritimo laukelių kiekis, M – robotų kiekis, K – sienų skaičius.

Toliau pateikta M eilučių po du sveikuosius skaičius x_i ir a_i – i-tojo roboto pradinė sekcija bei įvesta komanda.

Paskutinėje eilutėje pateikta K sveikųjų skaičių y_i – i-tosios sienos sekcija.

Robotai ir sienos pateikti sekcijų didėjimo tvarka. Visos sekcijos yra skirtingos.

Vienoje eilutėje išveskite M tarpais atskirtų skaičių, nurodančių, kokiose sekcijose robotai atsidurs simuliacijos pabaigoje. Sekcijų numerius galite išvesti bet kokia tvarka.

• 3 ≤ N ≤ 1 000 000 000
• 1 ≤ M ≤ 200 000
• 0 ≤ K ≤ 200 000
• M + K ≤ N
• 0 ≤ a_i ≤ N - 1
• 1 ≤ x_i, y_i ≤ N
• Robotai pateikti jų pradinės sekcijos didėjimo tvarka.
• Sienos pateiktos jų pradinės sekcijos didėjimo tvarka.
• Jokioje sekcijoje nebus daugiau nei vienas objektas (siena ar robotas).