35496번 - 여기는 몇 층일까

국민대학교에는 연결 통로로 이어져 있으면서도 층수 체계가 서로 다른 건물들이 존재한다.

모든 건물에서 한 층의 높이는 서로 같으며, 연결 통로는 서로 다른 두 건물에서 같은 높이에 있는 층을 연결한다.

건물은 $1$번 건물부터 $N$번 건물까지 순서대로 번호가 붙어 있다.

$i$번 건물과 $i+1$번 건물을 잇는 연결 통로는 $i$번 건물의 $A_i$층과 $i+1$번 건물의 $B_i$층을 연결한다.

또한, 모든 건물은 지상과 지하로 층이 무한히 이어진다고 가정한다.

이때 다음 쿼리를 수행하는 프로그램을 작성하자.

• l r x: $l$번 건물의 지상 $x$층과 같은 높이에 있는 위치가 $r$번 건물에서 몇 층인지 출력한다.

첫 번째 줄에 건물의 개수 $N$과 쿼리의 개수 $Q$가 공백으로 구분되어 주어진다.

그다음 줄부터 $N-1$개의 줄에 걸쳐, 각 줄에 두 정수 $A_i, B_i$가 공백으로 구분되어 주어진다.

그다음 줄부터 $Q$개의 줄에 걸쳐, 쿼리가 한 줄에 하나씩 주어진다.

각 쿼리에 대해서 정답을 한 줄에 하나씩 순서대로 출력한다.

지하층은 B 를 앞에 붙여 표현한다. 예를 들어, 지하 $6$층은 B6 으로 출력한다.

• 입력으로 주어지는 모든 수는 정수이다.
• $2 \leq N, Q \leq 500 \ 000$
• $1 \leq A_i, B_i \leq 100$
• $1 \leq i \leq N - 1$
• $1 \leq l < r \leq N$
• $1 \leq x \leq 100$
• 입력으로 주어지는 $x$는 지상층이다.
• $0$층은 존재하지 않는다.