Иван Царевич Өлмес Кощейдің өлімін іздеп жүріп, сиқырлы тоғайға тап болды. Баба Яганың айтуынша, онда $n$ дана емен ағашы өседі, олардың ішінде дәл $k$ емен әрқашан шындықты айтады, ал қалғандары әрқашан өтірік айтады.
Әрі қарай қайда бару керектігін білу үшін Царевич емендерден кейінгі бағытты білуі керек. Алайда ол өте сақ болуы тиіс, өйткені егер ол өтірікші емендердің бірінің кеңесіне ерсе, бір көзді Лихо торуылдап тұрған батпаққа кіріп кетеді.
Қай емендерге сенуге болатынын түсіну үшін Иван әрбір еменге мынадай сұрақ қойды: «$i$-ші емен, айтшы, $a_i$-ші емен әрқашан шындықты айта ма?» Бірақ ол алған жауаптарымен не істеу керектігін түсіне алмады.
Иван Царевичке сұрақтардан қорытынды шығаруға көмектесіңіз. Әрбір емен үшін оның әрқашан шындықты айтатынын, әрқашан өтірік айтатынын немесе ақпарат жеткіліксіз екенін анықтаңыз. Егер Баба Яга Иван Царевичті алдап, кіріс деректерін қанағаттандыратын емендердің ешқандай мүмкін конфигурациясы болмаса, жалғыз $-2$ санын шығарыңыз.
Кіріс деректері
Бірінші жолда сәйкесінше емендердің санын және олардың қаншасы әрқашан шындықты айтатынын білдіретін екі бүтін сан $n$ мен $k$ ($1 \le n \le 5 \cdot 10^5$, $0 \le k \le n$) берілген.
Келесі $n$ жолдың $i$-шісінде екі бүтін сан $a_i$ және $b_i$ ($1 \le a_i \le n$, $0 \le b_i \le 1$) берілген, бұл $i$-ші еменнен $a_i$-ші еменнің әрқашан шындықты айтатыны-айтпайтыны сұралғанын және егер $b_i = 1$ болса, жауап «иә», әйтпесе «жоқ» болғанын білдіреді.
Шығыс деректері
Егер кіріс деректері қайшылықты болса, бір бүтін сан $-2$ шығарыңыз.
Әйтпесе, емендердің шындықты айтатыны туралы қорытындыларды білдіретін $n$ бүтін сан $t_1, t_2, \dots, t_n$ шығарыңыз. Олар келесі мәндерді қабылдай алады:
- $t_i = 1$, егер $i$-ші емен әрқашан шындықты айтса;
- $t_i = -1$, егер $i$-ші емен әрқашан өтірік айтса;
- $t_i = 0$, егер қолда бар деректерден $i$-ші еменнің әрқашан өтірік айтатынын немесе шындықты айтатынын анықтау мүмкін болмаса.
Мысалдар
Кіріс 1
6 4 2 0 1 0 3 1 3 0 3 0 6 1
Шығыс 1
0 0 -1 1 1 1
Кіріс 2
3 1 2 0 3 0 1 0
Шығыс 2
-2