몬스터 격퇴 원정단

메이플 월드의 엘나스 마을은 눈으로 덮인 마을이다. 엘나스 마을 주변에는 폐광이 있어 여러 몬스터가 살고 있다. 어느 날, 폐광의 몬스터들이 마을을 습격하기 위해 모여든다는 소식이 전해졌다. 다양한 정보원을 통해 마을을 공격하려는 몬스터들의 수가 $N$ 마리라는 점과, 각 몬스터의 체력과 몬스터 속성에 대한 정보를 얻었다.

당신은 몬스터들의 공격을 받기 전에 몬스터 격퇴 원정단을 꾸려 선제적으로 몬스터를 공격하기 위해 몬스터 퇴치 원정단에 참가할 용사를 모집하였다. 몬스터 퇴치를 위해 자원하여 모인 용사의 수는 $M$ 명이며, 다행스럽게도 $M$은 $N$보다 크거나 같다. 당신은 일렬로 줄 서 있는 $M$ 명의 용사 가운데 연속한 $N$ 명을 선택하여 몬스터 격퇴 원정단을 구성하려고 한다. 이처럼 원정단을 구성하는 방법은 총 $M-N+1$ 가지가 있다.

몬스터의 체력은 정수로 표현되고, 용사 공격력도 정수로 표시된다. 각 용사와 각 몬스터는 모두 불의 속성과 얼음의 속성 중 하나의 속성을 가지고 있다. 용사가 다른 속성의 몬스터를 공격하면 용사의 공격력만큼 몬스터의 체력이 줄어들지만, 같은 속성의 몬스터를 공격하면 용사의 공격력의 절반만큼 몬스터의 체력이 줄어든다. 만약, 용사의 공격력이 홀수라면 버림을 한다. 즉, 공격력이 $5$인 용사가 같은 속성의 몬스터를 공격하면 몬스터의 체력이 $2$만큼 줄어든다.

원정단을 구성하고 나면 원정단에 속한 용사들은 서로 다른 몬스터를 한 마리씩 골라서 한 번씩 공격할 수 있다. 원정이 성공하기 위해서는 모든 용사의 공격이 끝난 후 모든 몬스터의 체력이 $0$ 이하가 되어야 한다.

$M-N+1$ 가지의 모든 가능한 원정단 구성에 대해 원정의 성공 여부를 알아내는 프로그램을 작성하시오.

입력 형식

첫 줄에 몬스터의 수 $N$과 용사의 수 $M$이 공백으로 구분되어 주어진다. ($1 \le N \le M \le 100\,000$)

이어지는 $N$ 개의 줄의 $i$ 번째 줄에는 $i$ 번째 몬스터의 정보를 나타내는 두 정수 $S_i$와 $A_i$가 공백으로 구분되어 주어진다. $S_i$는 몬스터의 속성을 의미하고, $A_i$는 몬스터의 체력을 의미한다. $S_i = 0$일 경우 몬스터는 불의 속성, $S_i = 1$일 경우 몬스터는 얼음의 속성을 가지고 있음을 의미한다. ($0 \le S_i \le 1;$ $1 \le A_i \le 1\,000\,000\,000$)

이어지는 $M$ 개의 줄의 $i$ 번째 줄에는 $i$ 번째 용사의 정보를 나타내는 두 정수 $T_i$와 $B_i$가 공백으로 구분되어 주어진다. $T_i$는 용사의 속성을 의미하고, $B_i$는 용사의 공격력을 의미한다. $T_i = 0$인 경우 용사는 불의 속성, $T_i = 1$인 경우 용사는 얼음의 속성을 가지고 있음을 의미한다. ($0 \le T_i \le 1;$ $1 \le B_i \le 1\,000\,000\,000$)

출력 형식

첫 줄에 길이가 $M-N+1$인 문자열을 출력한다.

문자열의 $i$ 번째 문자가 0인 경우, $i$ 번째 용사부터 $i+N-1$ 번째 용사까지 구성된 원정대는 목표를 달성할 수 없음을 의미한다.

문자열의 $i$ 번째 문자가 1인 경우, $i$ 번째 용사부터 $i+N-1$ 번째 용사까지 구성된 원정대는 목표를 달성할 수 있음을 의미한다.

예제

2 4
0 7
1 10
1 7
0 15
0 10
1 5

110

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞혀야 그 종류에 배정된 점수를 받을 수 있다.

해설