고대 유적 탐험

당신은 보물을 찾기 위해 고대 유적을 탐험하고 있었다.

함정과 미로를 모두 해결해 보물창고의 앞에 도달한 당신!! 그러나 마지막 관문에 부딪혔다.

보물창고의 문을 열려면 K진수로 되어있는 N자리의 비밀번호를 입력해야 했던 것이다!

유적에 살던 주민들은 누구나 비밀번호를 알 수 있게 했지만, 외부인으로 부터 보물을 보호하기 위해 암호를 알아내는데 시간과 노력이 매우 많이 필요하게 해 놓았다.

보물 창고의 문에는 수식 f(x)가 적혀 있었고, N개의 숫자 또한 같이 있었다.

N개의 숫자를 차례대로 A_i라고 했을 때, f(A_i)의 1의 자리 숫자를 순서대로 나열한 것이 문을 열기 위한 비밀번호였다.

하지만 안타깝게도 이는 고대에서나 오래 걸리는 것이지, 현대에는 컴퓨터가 있다.

당신은 특기인 프로그래밍 능력을 살려 비밀번호를 구해내기로 했다.

비밀번호의 각 자리를 구하는 프로그램을 만들어 보물창고의 문을 열어보자!

입력

첫 줄에 K(2 ≤ K ≤ 36)와 N(1 ≤ N ≤ 100,000)이 공백을 사이에 두고 주어진다.

두 번째 줄에는 f(x)에 해댱하는 수식이 후위표기법으로 주어진다. 수식은 100,000자를 넘지 않는다.

수식의 각 항은 공백으로 구분되며, 항으로는 다음의 것들이 올 수 있다.

K진수의 숫자가 주어진다. 0부터 9까지의 숫자는 아라비아 숫자(0 ~ 9)로 주어지며, K > 10일 경우 10 이상의 숫자는 대문자 A, B, C, … 에 대응되어 주어진다. 주어진 숫자는 두 자리 이상일 수 있으며 십진수로 2,000,000,000을 넘지 않는다.
f(x)의 x는 소문자 x로 주어진다.
덧셈 연산자는 + 문자로 주어진다.
뺄셈 연산자는 - 문자로 주어진다.
곱셈 연산자는 * 문자로 주어진다.

세 번째 줄부터 한 줄에 하나씩 총 N줄에 걸쳐 K진수로 A_i가 주어진다. 각 값은 십진수로 2,000,000,000을 넘지 않는다.

잘못된 입력은 주어지지 않으며, 항상 답을 구할 수 있음이 보장된다.

출력

총 N줄에 걸쳐, 각 줄에 f(A_i)의 1의 자리 숫자를 출력한다.

각 숫자는 K진수이므로, 0~9에서 A~Z까지 올 수 있다.

입력으로 주어진 모든 x에 대하여 f(x) 결과는 음수가 아님을 보장한다.

부분문제

예제

출처

CEOI 2007 – Nasty|wram Ly

고대 유적 탐험 1s 64MB