동전 게임

영희와 동수는 동전 던지기 게임을 하고 있다. 이 게임은 K번 라운드로 구성되고 다음과 같은 규칙들을 따른다:

• 한 라운드에서 영희와 동수는 한 번씩 동전을 던지고 항상 영희가 먼저 던진다.

• 동전을 던져 앞면이 나오면 1점을 얻고, 뒷면이 나오면 점수를 얻지 못한다.

• 한 명이 남은 기회에 모든 점수를 얻더라도 상대방이 현재까지 얻은 점수보다 작게 되면 게임 도중 어떤 시점에서도 게임은 바로 끝난다.

0이상 K이하인 임의의 정수 M과 N에 대해서, 이것이 항상 게임이 끝난 후 영희와 동수가 얻는 점수가 되는 것은 아니다. 예를 들어서, \(K = 2\)인 경우에, M과 N의 모든 경우에 대해서, 이것이 영희와 동수가 얻는 점수가 될 수 있는 지의 여부는 다음 표와 같다:

        M
        N
        영희, 동수의 점수가 될 가능성




        0
        0
        가능


        0
        1
        가능


        0
        2
        불가능


        1
        0
        가능


        1
        1
        가능


        1
        2
        가능


        2
        0
        가능


        2
        1
        가능


        2
        2
        가능

위 표에서 영희와 동수의 점수가 0과 2가 되는 것이 불가능한 이유는 두 번째 라운드에서 영희가 뒷면이 나와서 점수를 얻지 못하는 순간 게임의 규칙 3에 의해서 0과 1로 게임이 끝나기 때문이다.

0이상 K이하인 정수 M과 N이 주어질 때, 이 두 정수가 각각 영희와 동수의 점수가 될 수 있는지 여부를 판별하는 프로그램을 작성하시오.

※ 이 문제의 채점 데이터는 공개된 공식 데이터가 없어 재구성한 것입니다. 문제 지문은 원본(정보올림피아드 기출)을 따릅니다.

첫 줄에 게임의 라운드 수를 나타내는 정수 \(K(1 \le K \le 1{,}000)\)가 주어진다. 두 번째 줄에는 입력의 개수를 나타내는 정수 \(C(1 \le C \le 100{,}000)\)가 주어진다. 다음 이어지는 C개의 줄 각각에는 하나의 입력을 나타내는 두 정수 M과 \(N(0 \le M,\) \(N \le K)\)이 주어진다.

출력은 C개의 줄로 구성된다. 게임에서 영희와 동수의 점수가 각각 M과 N이 될 수 있다면 1, 아니면 0을 각 줄에 출력한다.

생성자가 기록되지 않았습니다.

출처 올림피아드 > 한국정보올림피아드 > KOI 2015 > 2차 대회 > 고등부 3번 / 중등부 4번