6. Okultistický fundraising

Trojsten je chudobné občianske združenie. Preto niet divu, že sa našlo zopár vedúcich, ktorí sa rozhodli s tým niečo spraviť a založili fundraisingovú skupinu. Získavanie peňazí sa im však až tak nedarilo. Preto sa Vlejd rozhodol, že sa k nim pridá a ukáže im, ako sa to robí.

Poriadny fundraising sa samozrejme nedá robiť bez štipky okultizmu. Poprípade viac ako štipky. A to bolo to, čo priniesol do skupiny Vlejd. Neprešiel ani týždeň a všetci z nich počúvali Pentagramček a spievali si ho v sprche. Takisto už vedeli, že keď chcú ísť na nejaké dôležité stretnutie, musia zabiť dve panenské sliepky a vykúpať sa v ich krvi.

Najväčšou zmenou však boli posedenia u veštice. Ak totiž chcete vedieť, či od firmy získate peniaze, ktoré od nej žiadate, musíte ísť za špeciálnou okultistickou vešticou. Tá vám pomôže vyveštiť, či bude vyjednávanie úspešné alebo nie. Na to používa špeciálny balíček fundraising-tarotových kariet.

Funraising-tarotové karty sa od tých normálnych trochu líšia. Na oboch stranách majú napísané jedno číslo. Na začiatku veštenia vytiahne z balíčka \(n\) kariet a podá vám ich. Vy sa potom pre každú kartu rozhodnete, ktorá strana sa vám páči viac. Ak je súčet čísiel, ktoré si takto zvolíte rovný množstvu peňazí, ktoré od firmy žiadate, budete úspešný. V opačnom prípade vás však pošlú preč s prázdnymi rukami.

Vlejd chce u veštice trošku podvádzať. Keď mu podá karty, chce si vybrať strany nie podľa osobnej preferencie, ale tak, aby ich súčet bol rovný číslu \(s\) – sume peňazí, ktorú bude žiadať. Tak nakloní osud na svoju stranu a Trojsten bude zachránený. Táto úloha však vôbec nie je taká jednoduchá. Vybrať správnu stranu karty je ťažké a možno sa dokonca ani nedá získať súčet \(s\). Pokúste sa mu pomôcť a naprogramovať program, ktorý mu pre každú kartu povie, ktorú stranu si má vybrať.

Úloha

Na vstupe dostanete \(n\) dvojíc kladných čísiel. Z každej dvojice vyberte jedno číslo tak, že súčet vybratých čísiel je rovný číslu \(s\). Ak sa to nedá, vypíšte príslušnú hlášku.

Formát vstupu

Na prvom riadku je číslo \(n\) (\(1 \leq n \leq 1\,000\)) – počet dvojíc čísiel.

Na druhom riadku je číslo \(s\) (\(0 \leq s \leq 50\,000\)) – súčet, ktorý sa snažíme dosiahnuť.

Nasleduje \(n\) riadkov, každý obsahujúci dve čísla \(x_i\) a \(y_i\) (\(0 \leq x_i,y_i \leq 50\,000\)) popisujúce jednotlivé dvojice čísiel, ktoré boli na kartách.

Pre hodnoty premennej \(n\) naviac platia nasledovné obmedzenia:

• Vo vstupoch za \(3\) body je \(n \leq 20\).

• Vo vstupoch za \(5\) bodov je \(n \leq 50\)

Formát výstupu

Na výstup vypíšte v jednom riadku \(n\) znakov, každý z nich je alebo . Na pozícii \(i\) tohto reťazca je ak má Vlejd vybrať prvé číslo z dvojice a , ak má vybrať druhé. V prípade viacerých možností, ako sa dá dosiahnuť výsledný súčet \(s\) vypíšte ľubovoľnú z nich.

Ak nie je možné dosiahnuť súčet \(s\) vypíšte (bez úvodzoviek).

Príklady

Input:

3
12
3 5
4 2
4 7

Output:

122

Input:

3
15
3 5
4 2
4 7

Output:

A je to v ...