둥근 수

시간 제한2초메모리 제한256 MB

요약

각 질의에서 x의 숫자 k개를 정확히 지워 남은 수가 앞에 0이 없으면서 100의 배수가 될 수 있는지 판정하고, 가능하면 그런 결과 하나를 출력한다.

난이도: 보통10점 중 5점
유형: 그리디, 구현, 문자열, 수학
정답자: 아직 제출이 없습니다

문제

모든 사람은 둥근 수를 좋아한다. 이유는 여러 가지가 있지만, 가장 큰 이유는 예를 들어 100으로 나누어떨어지는 수는 기억하기가 훨씬 쉽다는 것이다. 안타깝게도 우리가 사는 세상에는 둥근 수가 그렇지 않은 수보다 훨씬 적다. 초등학교 1학년 페차는 이 사실을 매우 안타까워한다. 그래서 그는 자신만의 둥근 수 정의를 생각해 냈다.

페차의 정의에 따르면, 어떤 수에서 정확히 $k$ 개의 숫자를 지워서 앞에 0이 남지 않으면서 100으로 나누어떨어지는 수를 만들 수 있을 때만 그 수는 둥근 수이다. 예를 들어 $k = 2$ 일 때 10304는 둥근 수이고, 1000은 둥근 수가 아니다.

이제 페차는 어떤 수가 어떤 $k$ 에 대해 둥근 수인지 아닌지 알고 싶어 한다. 그를 도와주자.

입력

첫째 줄에는 페차가 알고 싶어 하는 수 $k$ 와 $x$ 의 쌍의 개수인 정수 $n$ 이 주어진다. 다음 $n$ 개의 줄에는 각각 두 개의 양의 정수 $k$ 와 $x$ 가 주어진다. 모든 $k$ 는 해당하는 수 $x$ 의 자릿수보다 작다. 모든 수 $x$ 에는 앞에 0이 없다. 모든 수 $x$ 의 자릿수의 합은 $10^5$ 을 넘지 않는다.

출력

입력의 각 쌍 $k$ , $x$ 에 대해, 수 $x$ 가 주어진 $k$ 에 대해 둥근 수가 아니면 -1을 출력한다. 수 $x$ 가 주어진 $k$ 에 대해 둥근 수이면, 정확히 $k$ 개의 숫자를 지운 뒤 100으로 나누어떨어지게 된 수 $x$ 를 출력한다. 출력하는 수에는 앞에 0이 없어야 하지만, 0일 수는 있다.

예제1

예제 1
입력
```
3
2 10304
2 1000
3 1023
```
예상 출력
```
100
-1
0
```