트리 숫자 생성기

어느 날 영 안나는 트리를 이용해 숫자 생성기를 만드는 엉뚱한 생각을 떠올린다. 생성기는 법 m과 1번부터 n번까지 번호가 붙은 n개의 노드로 이루어진 내부 트리로 만들어진다. 트리의 각 노드에는 0부터 9까지의 한 자리 숫자가 하나씩 배정된다. 생성기는 [0, m) 범위의 정수를 만들어 내는 Get(a, b) 메서드를 제공한다. 두 인자 a와 b는 트리의 두 노드를 가리킨다. 생성기는 트리에서 a에서 b로 가는 경로를 따라가며, 경로 위의 모든 숫자(a와 b 노드의 숫자도 포함)를 이어 붙여 십진 정수 v를 얻는다. v는 매우 클 수 있고 앞에 0이 여러 개 붙을 수도 있다. Get(a, b)의 반환값은 v를 m으로 나눈 나머지이다.

트리와 안나의 숫자 생성기가 사용할 m이 주어질 때, q개의 질의 Get(a, b)의 반환값을 계산하라.

입력의 첫 줄에는 세 정수 n (2 ≤ n ≤ 2 · 105), m (1 ≤ m ≤ 109), q (1 ≤ q ≤ 2 · 105)가 주어진다.

다음 n − 1개 줄에는 트리의 간선이 주어진다. 각 줄에는 간선이 잇는 두 정수 x, y (1 ≤ x, y ≤ n)가 주어진다. 이 간선들이 트리를 이룸이 보장된다.

다음 n개 줄에는 0부터 9까지의 한 자리 숫자가 하나씩 주어진다. i번째 숫자는 i번 노드에 배정된다.

다음 q개 줄에는 질의 Get(a, b)를 나타내는 두 정수 a, b (1 ≤ a, b ≤ n)가 주어진다.

각 Get(a, b) 질의의 반환값을 한 줄에 하나씩 출력한다.