시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
4 초 512 MB 80 22 8 19.512%

문제

0번 부터 N-1번까지 번호가 매겨진 학생 N명이 있다. 선생님은 학생들을 위해 날마다 하나 이상의 프로젝트들을 준비한다. 각 프로젝트는 정해진 날에 학생들끼리 모인 팀에 의해 해결되어야한다. 물론 프로젝트들은 서로 다른 난이도를 가질 수 있다. 선생님은 각 프로젝트 별로 난이도에 따라 맡을 팀의 크기를 정해놓았다.

학생들마다 서로 들어갈 수 있는 팀의 크기가 다를 수 있다. 자세히 말하자면 i번 학생은 자신이 속하는 팀의 크기가 A[i]이상 B[i]이하가 되어야 한다. 각 날 별로 한 학생은 최대 하나의 팀에만 속할 수 있으며, 어떤 팀에도 속하지 않은 학생이 나올 수도 있다. 그리고 구성된 하나의 팀은 하나의 프로젝트만 맡는다.

선생님은 이미 다음 Q일 동안의 프로젝트들을 계획해놓았다. 선생님의 계획이 성사되도록 학생들이 팀을 구성할 수 있을지 판단하는 프로그램을 작성하시오.

N = 4명의 학생이 있고, Q = 2일 동안의 계획이 잡혀있다. 그리고 학생들이 속하는 팀 크기의 제한은 아래 표와 같다.

학생 0 1 2 3
A 1 2 2 2
B 2 3 3 4

첫째 날에는 M = 2개의 프로젝트가 계획 되어있다. 그리고 프로젝트를 해결하기 위해 정해놓은 팀의 크기는 K[0] = 1, K[1] = 3이다. 이 계획은 0번 학생이 팀의 크기가 1인 프로젝트에 참여 하고, 나머지 학생들이 팀의 크기가 3인 프로젝트에 참여하면 성사될 수 있다.

둘째 날에도 M = 2개의 프로젝트가 계획되어 있으며, 프로젝트를 해결하기 위해 정해놓은 팀의 크기는 K[0] = 1, K[1] = 1이다. 크기가 1인 팀에 들어갈 수 있는 학생이 한 명 밖에 없으므로이 경우에는 계획이 성사될 수 없다.

모든 학생에 대한 정보가 주어진다: N, A, B와 총 Q개의 날에 해당하는 정보가 주어지는데, 하루 에 하나씩이다. 각 정보는 그날 주어진 프로젝트의 수 M과 길이 M인 수열 K로 이루어지는데, K는 각 프로젝트에 필요한 팀의 크기를 저장하고 있다. 각각의 날마다, 여러분의 프로그램은 모든 팀을 구성할 수 있는지 여부를 리턴해야 한다.

다음 함수 init 와 can을 구현해야 한다:

  • init(N, A, B) — 그레이더는 맨 처음 이 함수를 정확히 한 번만 호출한다.
    • N: 학생의 수.
    • A: 길이가 N인 배열: A[i]는 학생 i가 들어갈 수 있는 최소의 팀 크기이다.
    • B: 길이가 N인 배열: B[i]는 학생 i가 들어갈 수 있는 최대의 팀 크기이다.
    • 이 함수는 리턴 값이 없다.
    • 각 i = 0, ..., N-1 인 경우에 대하여 1 ≤ A[i] ≤ B[i] ≤ N이 만족된다.
  • can(M, K) — init을 일단 호출한 뒤, 그레이더는 이 함수를 차례로 Q번 연속으로 호출하는데, 각 날짜에 대해서 한번씩 호출한다.
    • M: 이날 잡혀 있는 프로젝트의 수.
    • K: 길이 M인 배열로, 각각의 프로젝트에 정해진 팀 크기.
    • 이 함수의 리턴값은 만약 모든 팀을 구성할 수 있다면 1이고, 그렇지 못하면 0이다.
    • 1 ≤ M ≤ N 을 만족하며, 각각 i = 0, ..., M-1에 대하여 1 ≤ K[i] ≤ N 이다. 모든 K[i] 값들의 총합은 N을 넘을 수 있다.

입력

  • 1번 줄: N
  • 2번 ~ N+1번 줄: A[i] B[i]
  • N+2번 줄: Q
  • N+3 ~ N+Q+2번 줄: M K[0] K[1] … K[M - 1]

S가 모든 can(M, K)의 호출에서 M값들의 총합이라고 했을 때, 1 ≤ N ≤ 500,000, 1 ≤ Q ≤ 200,000, S ≤ 200,000

출력

각 날짜에 대해서 can의 리턴값을 출력한다.

예제 입력 1

4
2 4
1 2
2 3
2 3
2
2 1 3
2 1 1

예제 출력 1

1
0
W3sicHJvYmxlbV9pZCI6IjEwOTIxIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVkMzAwXHViNGU0IiwiZGVzY3JpcHRpb24iOiI8cD4wXHViYzg4IFx1YmQ4MFx1ZDEzMCBOLTFcdWJjODhcdWFlNGNcdWM5YzAgXHViYzg4XHVkNjM4XHVhYzAwIFx1YjllNFx1YWNhOFx1YzljNCBcdWQ1NTlcdWMwZGQgTlx1YmE4NVx1Yzc3NCBcdWM3ODhcdWIyZTQuIFx1YzEyMFx1YzBkZFx1YjJkOFx1Yzc0MCBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NDQgXHVjNzA0XHVkNTc0IFx1YjBhMFx1YjljOFx1YjJlNCBcdWQ1NThcdWIwOTggXHVjNzc0XHVjMGMxXHVjNzU4IFx1ZDUwNFx1Yjg1Y1x1YzgxZFx1ZDJiOFx1YjRlNFx1Yzc0NCBcdWM5MDBcdWJlNDRcdWQ1NWNcdWIyZTQuIFx1YWMwMSBcdWQ1MDRcdWI4NWNcdWM4MWRcdWQyYjhcdWIyOTQgXHVjODE1XHVkNTc0XHVjOWM0IFx1YjBhMFx1YzVkMCBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWIwN2NcdWI5YWMgXHViYWE4XHVjNzc4IFx1ZDMwMFx1YzVkMCBcdWM3NThcdWQ1NzQgXHVkNTc0XHVhY2IwXHViNDE4XHVjNWI0XHVjNTdjXHVkNTVjXHViMmU0LiBcdWJiM2NcdWI4NjAgXHVkNTA0XHViODVjXHVjODFkXHVkMmI4XHViNGU0XHVjNzQwIFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHViMDljXHVjNzc0XHViM2M0XHViOTdjIFx1YWMwMFx1YzljOCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWMxMjBcdWMwZGRcdWIyZDhcdWM3NDAgXHVhYzAxIFx1ZDUwNFx1Yjg1Y1x1YzgxZFx1ZDJiOCBcdWJjYzRcdWI4NWMgXHViMDljXHVjNzc0XHViM2M0XHVjNWQwIFx1YjUzMFx1Yjc3YyBcdWI5ZTFcdWM3NDQgXHVkMzAwXHVjNzU4IFx1ZDA2Y1x1YWUzMFx1Yjk3YyBcdWM4MTVcdWQ1NzRcdWIxOTNcdWM1NThcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDU1OVx1YzBkZFx1YjRlNFx1YjljOFx1YjJlNCBcdWMxMWNcdWI4NWMgXHViNGU0XHVjNWI0XHVhYzA4IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVkMzAwXHVjNzU4IFx1ZDA2Y1x1YWUzMFx1YWMwMCBcdWIyZTRcdWI5N2MgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNzkwXHVjMTM4XHVkNzg4IFx1YjlkMFx1ZDU1OFx1Yzc5MFx1YmE3NCBpXHViYzg4IFx1ZDU1OVx1YzBkZFx1Yzc0MCBcdWM3OTBcdWMyZTBcdWM3NzQgXHVjMThkXHVkNTU4XHViMjk0IFx1ZDMwMFx1Yzc1OCBcdWQwNmNcdWFlMzBcdWFjMDAgQVtpXVx1Yzc3NFx1YzBjMSBCW2ldXHVjNzc0XHVkNTU4XHVhYzAwIFx1YjQxOFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YWMwMSBcdWIwYTAgXHViY2M0XHViODVjIFx1ZDU1YyBcdWQ1NTlcdWMwZGRcdWM3NDAgXHVjZDVjXHViMzAwIFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWQzMDBcdWM1ZDBcdWI5Y2MgXHVjMThkXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YzViNFx1YjVhNCBcdWQzMDBcdWM1ZDBcdWIzYzQgXHVjMThkXHVkNTU4XHVjOWMwIFx1YzU0YVx1Yzc0MCBcdWQ1NTlcdWMwZGRcdWM3NzQgXHViMDk4XHVjNjJjIFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWFkNmNcdWMxMzFcdWI0MWMgXHVkNTU4XHViMDk4XHVjNzU4IFx1ZDMwMFx1Yzc0MCBcdWQ1NThcdWIwOThcdWM3NTggXHVkNTA0XHViODVjXHVjODFkXHVkMmI4XHViOWNjIFx1YjllMVx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMTIwXHVjMGRkXHViMmQ4XHVjNzQwIFx1Yzc3NFx1YmJmOCBcdWIyZTRcdWM3NGMgUVx1Yzc3YyBcdWIzZDlcdWM1NDhcdWM3NTggXHVkNTA0XHViODVjXHVjODFkXHVkMmI4XHViNGU0XHVjNzQ0IFx1YWNjNFx1ZDY4ZFx1ZDU3NFx1YjE5M1x1YzU1OFx1YjJlNC4gXHVjMTIwXHVjMGRkXHViMmQ4XHVjNzU4IFx1YWNjNFx1ZDY4ZFx1Yzc3NCBcdWMxMzFcdWMwYWNcdWI0MThcdWIzYzRcdWI4NWQgXHVkNTU5XHVjMGRkXHViNGU0XHVjNzc0IFx1ZDMwMFx1Yzc0NCBcdWFkNmNcdWMxMzFcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1Yzc0NFx1YzljMCBcdWQzMTBcdWIyZThcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG5cclxuPHA+TiA9IDRcdWJhODVcdWM3NTggXHVkNTU5XHVjMGRkXHVjNzc0IFx1Yzc4OFx1YWNlMCwgUSA9IDJcdWM3N2MgXHViM2Q5XHVjNTQ4XHVjNzU4IFx1YWNjNFx1ZDY4ZFx1Yzc3NCBcdWM3YTFcdWQ2MDBcdWM3ODhcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NzQgXHVjMThkXHVkNTU4XHViMjk0IFx1ZDMwMCBcdWQwNmNcdWFlMzBcdWM3NTggXHVjODFjXHVkNTVjXHVjNzQwIFx1YzU0NFx1Yjc5OCBcdWQ0NWNcdWM2NDAgXHVhYzE5XHViMmU0LjxcL3A+XHJcblxyXG48dGFibGUgY2xhc3M9XCJ0YWJsZSB0YWJsZS1ib3JkZXJlZFwiIHN0eWxlPVwid2lkdGg6MzAlXCI+XHJcblx0PHRoZWFkPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGg+XHVkNTU5XHVjMGRkPFwvdGg+XHJcblx0XHRcdDx0aD4wPFwvdGg+XHJcblx0XHRcdDx0aD4xPFwvdGg+XHJcblx0XHRcdDx0aD4yPFwvdGg+XHJcblx0XHRcdDx0aD4zPFwvdGg+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90aGVhZD5cclxuXHQ8dGJvZHk+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0aD5BPFwvdGg+XHJcblx0XHRcdDx0ZD4xPFwvdGQ+XHJcblx0XHRcdDx0ZD4yPFwvdGQ+XHJcblx0XHRcdDx0ZD4yPFwvdGQ+XHJcblx0XHRcdDx0ZD4yPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRoPkI8XC90aD5cclxuXHRcdFx0PHRkPjI8XC90ZD5cclxuXHRcdFx0PHRkPjM8XC90ZD5cclxuXHRcdFx0PHRkPjM8XC90ZD5cclxuXHRcdFx0PHRkPjQ8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdDxcL3Rib2R5PlxyXG48XC90YWJsZT5cclxuXHJcbjxwPlx1Y2NhYlx1YzlmOCBcdWIwYTBcdWM1ZDBcdWIyOTQgTSA9IDJcdWFjMWNcdWM3NTggXHVkNTA0XHViODVjXHVjODFkXHVkMmI4XHVhYzAwIFx1YWNjNFx1ZDY4ZCBcdWI0MThcdWM1YjRcdWM3ODhcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWQ1MDRcdWI4NWNcdWM4MWRcdWQyYjhcdWI5N2MgXHVkNTc0XHVhY2IwXHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWM4MTVcdWQ1NzRcdWIxOTNcdWM3NDAgXHVkMzAwXHVjNzU4IFx1ZDA2Y1x1YWUzMFx1YjI5NCBLWzBdID0gMSwgS1sxXSA9IDNcdWM3NzRcdWIyZTQuIFx1Yzc3NCBcdWFjYzRcdWQ2OGRcdWM3NDAgMFx1YmM4OCBcdWQ1NTlcdWMwZGRcdWM3NzQgXHVkMzAwXHVjNzU4IFx1ZDA2Y1x1YWUzMFx1YWMwMCAxXHVjNzc4IFx1ZDUwNFx1Yjg1Y1x1YzgxZFx1ZDJiOFx1YzVkMCBcdWNjMzhcdWM1ZWMgXHVkNTU4XHVhY2UwLCBcdWIwOThcdWJhMzhcdWM5YzAgXHVkNTU5XHVjMGRkXHViNGU0XHVjNzc0IFx1ZDMwMFx1Yzc1OCBcdWQwNmNcdWFlMzBcdWFjMDAgM1x1Yzc3OCBcdWQ1MDRcdWI4NWNcdWM4MWRcdWQyYjhcdWM1ZDAgXHVjYzM4XHVjNWVjXHVkNTU4XHViYTc0IFx1YzEzMVx1YzBhY1x1YjQyMCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHViMGEwXHVjNWQwXHViM2M0IE0gPSAyXHVhYzFjXHVjNzU4IFx1ZDUwNFx1Yjg1Y1x1YzgxZFx1ZDJiOFx1YWMwMCBcdWFjYzRcdWQ2OGRcdWI0MThcdWM1YjQgXHVjNzg4XHVjNzNjXHViYTcwLCBcdWQ1MDRcdWI4NWNcdWM4MWRcdWQyYjhcdWI5N2MgXHVkNTc0XHVhY2IwXHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWM4MTVcdWQ1NzRcdWIxOTNcdWM3NDAgXHVkMzAwXHVjNzU4IFx1ZDA2Y1x1YWUzMFx1YjI5NCBLWzBdID0gMSwgS1sxXSA9IDFcdWM3NzRcdWIyZTQuIFx1ZDA2Y1x1YWUzMFx1YWMwMCAxXHVjNzc4IFx1ZDMwMFx1YzVkMCBcdWI0ZTRcdWM1YjRcdWFjMDggXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWQ1NTlcdWMwZGRcdWM3NzQgXHVkNTVjIFx1YmE4NSBcdWJjMTZcdWM1ZDAgXHVjNWM2XHVjNzNjXHViYmMwXHViODVjXHVjNzc0IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWFjYzRcdWQ2OGRcdWM3NzQgXHVjMTMxXHVjMGFjXHViNDIwIFx1YzIxOCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmFhOFx1YjRlMCBcdWQ1NTlcdWMwZGRcdWM1ZDAgXHViMzAwXHVkNTVjIFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQ6IE4sIEEsIEJcdWM2NDAgXHVjZDFkIFFcdWFjMWNcdWM3NTggXHViMGEwXHVjNWQwIFx1ZDU3NFx1YjJmOVx1ZDU1OFx1YjI5NCBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0XHViMzcwLCBcdWQ1NThcdWI4ZTggXHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOVx1Yzc3NFx1YjJlNC4gXHVhYzAxIFx1YzgxNVx1YmNmNFx1YjI5NCBcdWFkZjhcdWIwYTAgXHVjOGZjXHVjNWI0XHVjOWM0IFx1ZDUwNFx1Yjg1Y1x1YzgxZFx1ZDJiOFx1Yzc1OCBcdWMyMTggTVx1YWNmYyBcdWFlMzhcdWM3NzQgTVx1Yzc3OCBcdWMyMThcdWM1ZjQgS1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzBcdWIyOTRcdWIzNzAsIEtcdWIyOTQgXHVhYzAxIFx1ZDUwNFx1Yjg1Y1x1YzgxZFx1ZDJiOFx1YzVkMCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVkMzAwXHVjNzU4IFx1ZDA2Y1x1YWUzMFx1Yjk3YyBcdWM4MDBcdWM3YTVcdWQ1NThcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHViMGEwXHViOWM4XHViMmU0LCBcdWM1ZWNcdWI3ZWNcdWJkODRcdWM3NTggXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQwIFx1YmFhOFx1YjRlMCBcdWQzMDBcdWM3NDQgXHVhZDZjXHVjMTMxXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTRcdWM5YzAgXHVjNWVjXHViZDgwXHViOTdjIFx1YjlhY1x1ZDEzNFx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBcdWQ1NjhcdWMyMTggaW5pdCBcdWM2NDAgY2FuXHVjNzQ0IFx1YWQ2Y1x1ZDYwNFx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQ6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+aW5pdChOLCBBLCBCKSAmbWRhc2g7IFx1YWRmOFx1YjgwOFx1Yzc3NFx1YjM1NFx1YjI5NCBcdWI5ZTggXHVjYzk4XHVjNzRjIFx1Yzc3NCBcdWQ1NjhcdWMyMThcdWI5N2MgXHVjODE1XHVkNjU1XHVkNzg4IFx1ZDU1YyBcdWJjODhcdWI5Y2MgXHVkNjM4XHVjZDljXHVkNTVjXHViMmU0LlxyXG5cdDx1bD5cclxuXHRcdDxsaT5OOiBcdWQ1NTlcdWMwZGRcdWM3NTggXHVjMjE4LjxcL2xpPlxyXG5cdFx0PGxpPkE6IFx1YWUzOFx1Yzc3NFx1YWMwMCBOXHVjNzc4IFx1YmMzMFx1YzVmNDogQVtpXVx1YjI5NCBcdWQ1NTlcdWMwZGQgaVx1YWMwMCBcdWI0ZTRcdWM1YjRcdWFjMDggXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWNkNWNcdWMxOGNcdWM3NTggXHVkMzAwIFx1ZDA2Y1x1YWUzMFx1Yzc3NFx1YjJlNC48XC9saT5cclxuXHRcdDxsaT5COiBcdWFlMzhcdWM3NzRcdWFjMDAgTlx1Yzc3OCBcdWJjMzBcdWM1ZjQ6IEJbaV1cdWIyOTQgXHVkNTU5XHVjMGRkIGlcdWFjMDAgXHViNGU0XHVjNWI0XHVhYzA4IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjZDVjXHViMzAwXHVjNzU4IFx1ZDMwMCBcdWQwNmNcdWFlMzBcdWM3NzRcdWIyZTQuPFwvbGk+XHJcblx0XHQ8bGk+XHVjNzc0IFx1ZDU2OFx1YzIxOFx1YjI5NCBcdWI5YWNcdWQxMzQgXHVhYzEyXHVjNzc0IFx1YzVjNlx1YjJlNC48XC9saT5cclxuXHRcdDxsaT5cdWFjMDEgaSA9IDAsIC4uLiwgTi0xIFx1Yzc3OCBcdWFjYmRcdWM2YjBcdWM1ZDAgXHViMzAwXHVkNTU4XHVjNWVjIDEgJmxlOyBBW2ldICZsZTsgQltpXSAmbGU7IE5cdWM3NzQgXHViOWNjXHVjODcxXHViNDFjXHViMmU0LjxcL2xpPlxyXG5cdDxcL3VsPlxyXG5cdDxcL2xpPlxyXG5cdDxsaT5jYW4oTSwgSykgJm1kYXNoOyBpbml0XHVjNzQ0IFx1Yzc3Y1x1YjJlOCBcdWQ2MzhcdWNkOWNcdWQ1NWMgXHViNGE0LCBcdWFkZjhcdWI4MDhcdWM3NzRcdWIzNTRcdWIyOTQgXHVjNzc0IFx1ZDU2OFx1YzIxOFx1Yjk3YyBcdWNjMjhcdWI4NDBcdWI4NWMgUVx1YmM4OCBcdWM1ZjBcdWMxOGRcdWM3M2NcdWI4NWMgXHVkNjM4XHVjZDljXHVkNTU4XHViMjk0XHViMzcwLCBcdWFjMDEgXHViMGEwXHVjOWRjXHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyBcdWQ1NWNcdWJjODhcdWM1MjkgXHVkNjM4XHVjZDljXHVkNTVjXHViMmU0LlxyXG5cdDx1bD5cclxuXHRcdDxsaT5NOiBcdWM3NzRcdWIwYTAgXHVjN2ExXHVkNjAwIFx1Yzc4OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWM4MWRcdWQyYjhcdWM3NTggXHVjMjE4LjxcL2xpPlxyXG5cdFx0PGxpPks6IFx1YWUzOFx1Yzc3NCBNXHVjNzc4IFx1YmMzMFx1YzVmNFx1Yjg1YywgXHVhYzAxXHVhYzAxXHVjNzU4IFx1ZDUwNFx1Yjg1Y1x1YzgxZFx1ZDJiOFx1YzVkMCBcdWM4MTVcdWQ1NzRcdWM5YzQgXHVkMzAwIFx1ZDA2Y1x1YWUzMC48XC9saT5cclxuXHRcdDxsaT5cdWM3NzQgXHVkNTY4XHVjMjE4XHVjNzU4IFx1YjlhY1x1ZDEzNFx1YWMxMlx1Yzc0MCBcdWI5Y2NcdWM1N2QgXHViYWE4XHViNGUwIFx1ZDMwMFx1Yzc0NCBcdWFkNmNcdWMxMzFcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNFx1YmE3NCAxXHVjNzc0XHVhY2UwLCBcdWFkZjhcdWI4MDdcdWM5YzAgXHViYWJiXHVkNTU4XHViYTc0IDBcdWM3NzRcdWIyZTQuPFwvbGk+XHJcblx0XHQ8bGk+MSAmbGU7IE0gJmxlOyBOIFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWJhNzAsIFx1YWMwMVx1YWMwMSBpID0gMCwgLi4uLCBNLTFcdWM1ZDAgXHViMzAwXHVkNTU4XHVjNWVjIDEgJmxlOyBLW2ldICZsZTsgTiBcdWM3NzRcdWIyZTQuIFx1YmFhOFx1YjRlMCBLW2ldIFx1YWMxMlx1YjRlNFx1Yzc1OCBcdWNkMWRcdWQ1NjlcdWM3NDAgTlx1Yzc0NCBcdWIxMThcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9saT5cclxuXHQ8XC91bD5cclxuXHQ8XC9saT5cclxuPFwvdWw+XHJcbiIsImlucHV0IjoiPHVsPlxyXG5cdDxsaT4xXHViYzg4IFx1YzkwNDogTjxcL2xpPlxyXG5cdDxsaT4yXHViYzg4IH4gTisxXHViYzg4IFx1YzkwNDogQVtpXSBCW2ldPFwvbGk+XHJcblx0PGxpPk4rMlx1YmM4OCBcdWM5MDQ6IFE8XC9saT5cclxuXHQ8bGk+TiszIH4gTitRKzJcdWJjODggXHVjOTA0OiBNIEtbMF0gS1sxXSAmaGVsbGlwOyBLW00gLSAxXTxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlNcdWFjMDAgXHViYWE4XHViNGUwIGNhbihNLCBLKVx1Yzc1OCBcdWQ2MzhcdWNkOWNcdWM1ZDBcdWMxMWMgTVx1YWMxMlx1YjRlNFx1Yzc1OCBcdWNkMWRcdWQ1NjlcdWM3NzRcdWI3N2NcdWFjZTAgXHVkNTg4XHVjNzQ0IFx1YjU0YywmbmJzcDsxICZsZTsgTiAmbGU7IDUwMCwwMDAsIDEgJmxlOyBRICZsZTsgMjAwLDAwMCwgUyAmbGU7IDIwMCwwMDA8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHViMGEwXHVjOWRjXHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyBjYW5cdWM3NTggXHViOWFjXHVkMTM0XHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMDkyMSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlRlYW1zIiwiZGVzY3JpcHRpb24iOiI8cD5UaGVyZSBpcyBhIGNsYXNzIG9mIE4gc3R1ZGVudHMsIG51bWJlcmVkIDAgdGhyb3VnaCBOLTEuIEV2ZXJ5IGRheSB0aGUgdGVhY2hlciBvZiB0aGUgY2xhc3MgaGFzIHNvbWUgcHJvamVjdHMgZm9yIHRoZSBzdHVkZW50cy4gRWFjaCBwcm9qZWN0IGhhcyB0byBiZSBjb21wbGV0ZWQgYnkgYSB0ZWFtIG9mIHN0dWRlbnRzIHdpdGhpbiB0aGUgc2FtZSBkYXkuIFRoZSBwcm9qZWN0cyBtYXkgaGF2ZSB2YXJpb3VzIGRpZmZpY3VsdHkuIEZvciBlYWNoIHByb2plY3QsIHRoZSB0ZWFjaGVyIGtub3dzIHRoZSBleGFjdCBzaXplIG9mIGEgdGVhbSB0aGF0IHNob3VsZCB3b3JrIG9uIGl0LjxcL3A+XHJcblxyXG48cD5EaWZmZXJlbnQgc3R1ZGVudHMgbWF5IHByZWZlciBkaWZmZXJlbnQgdGVhbSBzaXplcy4gTW9yZSBwcmVjaXNlbHksIHN0dWRlbnQgY2FuIG9ubHkgYmUgYXNzaWduZWQgdG8gYSB0ZWFtIG9mIHNpemUgYmV0d2VlbiBBW2ldIGFuZCBCW2ldIGluY2x1c2l2ZS4gT24gZWFjaCBkYXksIGEgc3R1ZGVudCBtYXkgYmUgYXNzaWduZWQgdG8gYXQgbW9zdCBvbmUgdGVhbS4gU29tZSBzdHVkZW50cyBtaWdodCBub3QgYmUgYXNzaWduZWQgdG8gYW55IHRlYW1zLiBFYWNoIHRlYW0gd2lsbCB3b3JrIG9uIGEgc2luZ2xlIHByb2plY3QuPFwvcD5cclxuXHJcbjxwPlRoZSB0ZWFjaGVyIGhhcyBhbHJlYWR5IGNob3NlbiB0aGUgcHJvamVjdHMgZm9yIGVhY2ggb2YgdGhlIG5leHQgUSBkYXlzLiBGb3IgZWFjaCBvZiB0aGVzZSBkYXlzLCBkZXRlcm1pbmUgd2hldGhlciBpdCBpcyBwb3NzaWJsZSB0byBhc3NpZ24gc3R1ZGVudHMgdG8gdGVhbXMgc28gdGhhdCB0aGVyZSBpcyBvbmUgdGVhbSB3b3JraW5nIG9uIGVhY2ggcHJvamVjdC48XC9wPlxyXG5cclxuPHA+U3VwcG9zZSB0aGVyZSBhcmUgTiA9IDQgc3R1ZGVudHMgYW5kIFEgPSAyIGRheXMuIFRoZSBzdHVkZW50cyZyc3F1bzsgY29uc3RyYWludHMgb24gdGVhbSBzaXplcyBhcmUgZ2l2ZW4gaW4gdGhlIHRhYmxlIGJlbG93LjxcL3A+XHJcblxyXG48dGFibGUgY2xhc3M9XCJ0YWJsZSB0YWJsZS1ib3JkZXJlZFwiIHN0eWxlPVwibGluZS1oZWlnaHQ6MjAuNzk5OTk5MjM3MDYwNXB4OyB3aWR0aDoyNDZweFwiPlxyXG5cdDx0aGVhZD5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRoPlN0dWRlbnQ8XC90aD5cclxuXHRcdFx0PHRoPjA8XC90aD5cclxuXHRcdFx0PHRoPjE8XC90aD5cclxuXHRcdFx0PHRoPjI8XC90aD5cclxuXHRcdFx0PHRoPjM8XC90aD5cclxuXHRcdDxcL3RyPlxyXG5cdDxcL3RoZWFkPlxyXG5cdDx0Ym9keT5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRoPkE8XC90aD5cclxuXHRcdFx0PHRkPjE8XC90ZD5cclxuXHRcdFx0PHRkPjI8XC90ZD5cclxuXHRcdFx0PHRkPjI8XC90ZD5cclxuXHRcdFx0PHRkPjI8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGg+QjxcL3RoPlxyXG5cdFx0XHQ8dGQ+MjxcL3RkPlxyXG5cdFx0XHQ8dGQ+MzxcL3RkPlxyXG5cdFx0XHQ8dGQ+MzxcL3RkPlxyXG5cdFx0XHQ8dGQ+NDxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0PFwvdGJvZHk+XHJcbjxcL3RhYmxlPlxyXG5cclxuPHA+T24gdGhlIGZpcnN0IGRheSB0aGVyZSBhcmUgTSA9IDIgcHJvamVjdHMuIFRoZSByZXF1aXJlZCB0ZWFtIHNpemVzIGFyZSBLWzBdID0gMSBhbmQgS1sxXSA9IDMuIFRoZXNlIHR3byB0ZWFtcyBjYW4gYmUgZm9ybWVkIGJ5IGFzc2lnbmluZyBzdHVkZW50IDAgdG8gYSB0ZWFtIG9mIHNpemUgMSBhbmQgdGhlIHJlbWFpbmluZyB0aHJlZSBzdHVkZW50cyB0byBhIHRlYW0gb2Ygc2l6ZSAzLjxcL3A+XHJcblxyXG48cD5PbiB0aGUgc2Vjb25kIGRheSB0aGVyZSBhcmUgTSA9IDIgcHJvamVjdHMgYWdhaW4sIGJ1dCB0aGlzIHRpbWUgdGhlIHJlcXVpcmVkIHRlYW0gc2l6ZXMgYXJlIEtbMF0gPSAxIGFuZCBLWzFdID0gMS4gSW4gdGhpcyBjYXNlIGl0IGlzIG5vdCBwb3NzaWJsZSB0byBmb3JtIHRoZSB0ZWFtcywgYXMgdGhlcmUgaXMgb25seSBvbmUgc3R1ZGVudCB3aG8gY2FuIGJlIGluIGEgdGVhbSBvZiBzaXplIDEuPFwvcD5cclxuXHJcbjxwPllvdSBhcmUgZ2l2ZW4gdGhlIGRlc2NyaXB0aW9uIG9mIGFsbHN0dWRlbnRzOiBOLCBBLCBhbmQgQiwgYXMgd2VsbCBhcyBhIHNlcXVlbmNlIG9mIFEgcXVlc3Rpb25zICZtZGFzaDsgb25lIGFib3V0IGVhY2ggZGF5LiBFYWNoIHF1ZXN0aW9uIGNvbnNpc3RzIG9mIHRoZSBudW1iZXIgTSBvZiBwcm9qZWN0cyBvbiB0aGF0IGRheSBhbmQgYSBzZXF1ZW5jZSBLIG9mIGxlbmd0aCBNIGNvbnRhaW5pbmcgdGhlIHJlcXVpcmVkIHRlYW0gc2l6ZXMuIEZvciBlYWNoIHF1ZXN0aW9uLCB5b3VyIHByb2dyYW0gbXVzdCByZXR1cm4gd2hldGhlciBpdCBpcyBwb3NzaWJsZSB0byBmb3JtIGFsbCB0aGUgdGVhbXMuPFwvcD5cclxuXHJcbjxwPllvdSBuZWVkIHRvIGltcGxlbWVudCB0aGUgZnVuY3Rpb25zIGluaXQgYW5kIGNhbjo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5pbml0KE4sIEEsIEIpICZtZGFzaDsgVGhlIGdyYWRlciB3aWxsIGNhbGwgdGhpcyBmdW5jdGlvbiBmaXJzdCBhbmQgZXhhY3RseSBvbmNlLlxyXG5cdDx1bD5cclxuXHRcdDxsaT5OOiB0aGUgbnVtYmVyIG9mIHN0dWRlbnRzLjxcL2xpPlxyXG5cdFx0PGxpPkE6IGFuIGFycmF5IG9mIGxlbmd0aCBOOiBBW2ldIGlzIHRoZSBtaW5pbXVtIHRlYW0gc2l6ZSBmb3Igc3R1ZGVudCBpLjxcL2xpPlxyXG5cdFx0PGxpPkI6IGFuIGFycmF5IG9mIGxlbmd0aCBOOiBCW2ldIGlzIHRoZSBtYXhpbXVtIHRlYW0gc2l6ZSBmb3Igc3R1ZGVudCBpLjxcL2xpPlxyXG5cdFx0PGxpPlRoZSBmdW5jdGlvbiBoYXMgbm8gcmV0dXJuIHZhbHVlLjxcL2xpPlxyXG5cdFx0PGxpPllvdSBtYXkgYXNzdW1lIHRoYXQgMSAmbGU7IEFbaV0gJmxlOyBCW2ldICZsZTsgTiBmb3IgZWFjaCBpID0gMCwgLi4uLCBOLTEuPFwvbGk+XHJcblx0PFwvdWw+XHJcblx0PFwvbGk+XHJcblx0PGxpPmNhbihNLCBLKSAmbWRhc2g7IEFmdGVyIGNhbGxpbmcgaW5pdCBvbmNlLCB0aGUgZ3JhZGVyIHdpbGwgY2FsbCB0aGlzIGZ1bmN0aW9uIFEgdGltZXMgaW4gYSByb3csIG9uY2UgZm9yIGVhY2ggZGF5LlxyXG5cdDx1bD5cclxuXHRcdDxsaT5NOiB0aGUgbnVtYmVyIG9mIHByb2plY3RzIGZvciB0aGlzIGRheS48XC9saT5cclxuXHRcdDxsaT5LOiBhbiBhcnJheSBvZiBsZW5ndGggTSBjb250YWluaW5nIHRoZSByZXF1aXJlZCB0ZWFtIHNpemUgZm9yIGVhY2ggb2YgdGhlc2UgcHJvamVjdHMuPFwvbGk+XHJcblx0XHQ8bGk+VGhlIGZ1bmN0aW9uIHNob3VsZCByZXR1cm4gMSBpZiBpdCBpcyBwb3NzaWJsZSB0byBmb3JtIGFsbCB0aGUgcmVxdWlyZWQgdGVhbXMgYW5kIDAgb3RoZXJ3aXNlLjxcL2xpPlxyXG5cdFx0PGxpPllvdSBtYXkgYXNzdW1lIHRoYXQgMSAmbGU7IE0gJmxlOyBOLCBhbmQgdGhhdCBmb3IgZWFjaCBpID0gMCwgLi4uLCBNLTEgd2UgaGF2ZSAxICZsZTsgS1tpXSAmbGU7IE4uIE5vdGUgdGhhdCB0aGUgc3VtIG9mIGFsbCBLW2ldIG1heSBleGNlZWQgTi48XC9saT5cclxuXHQ8XC91bD5cclxuXHQ8XC9saT5cclxuPFwvdWw+XHJcbiIsImlucHV0IjoiPHVsPlxyXG5cdDxsaT5saW5lIDE6IE48XC9saT5cclxuXHQ8bGk+bGluZXMgMiwgJmhlbGxpcDssIE4gKyAxOiBBW2ldIEJbaV08XC9saT5cclxuXHQ8bGk+bGluZSBOICsgMjogUTxcL2xpPlxyXG5cdDxsaT5saW5lcyBOICsgMywgJmhlbGxpcDssIE4gKyBRICsgMjogTSBLWzBdIEtbMV0gJmhlbGxpcDsgS1tNIC0gMV08XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5MZXQgdXMgZGVub3RlIGJ5IHRoZSBzdW0gb2YgdmFsdWVzIG9mIE0gaW4gYWxsIGNhbGxzIHRvIGNhbihNLCBLKS4mbmJzcDsxICZsZTsgTiAmbGU7IDUwMCwwMDAsIDEgJmxlOyBRICZsZTsgMjAwLDAwMCwgUyAmbGU7IDIwMCwwMDA8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBxdWVzdGlvbiwgcHJpbnRzIHRoZSByZXR1cm4gdmFsdWUgb2YgY2FuLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Olympiad > International Olympiad in Informatics > IOI 2015 3번