위대한 힘의 물약

옛날 옛적에, 주술사들의 땅에서는 모든 사람이 하늘 높이 솟은 콩나무 위에서 살았다. 각 주술사에게는 0과 N − 1 사이의 고유한 식별 번호 i와, 지면에서 얼마나 높이 사는지를 나타내는 고도 값 Hi가 있었다. 두 고도 사이의 거리는 두 값의 차의 절댓값이다.

모든 주술사는 평화롭게 함께 살았지만, 그중 한 명이 세계적으로 유명한 위대한 힘의 물약의 제조법을 훔쳤다. 자신의 흔적을 감추기 위해 도둑은 땅에 저주를 걸었다. 대부분의 주민이 더 이상 서로를 신뢰할 수 없게 되었다...

매우 어려운 상황 속에서도 선한 조사관단은 저주에 대해 다음과 같은 정보를 얻었다.

• 저주가 처음 발동하면 모든 사람이 서로를 신뢰하지 않게 된다.
• 저주는 불안정하다. 매일이 끝날 때(정확히 자정에) 한 쌍의 주술사가 서로를 신뢰하기 시작하거나 신뢰를 멈춘다.
• 안타깝게도, 각 주술사는 어느 순간에도 최대 D명의 다른 사람만 신뢰한다.

그들은 또한 누가 누구를 신뢰했는지에 대한 기록을 복원했다. 각 밤마다 어떤 한 쌍의 주술사가 서로를 신뢰하기 시작했는지 혹은 멈췄는지를 알고 있다.

그들은 도둑이 사악한 주술사에게 제조법을 속삭였다고 믿는다. 발각을 피하기 위해, 두 사람은 각자의 신뢰하는 친구 중 한 명의 집을 방문했다. 방문 중에 도둑은 창문을 통해 사악한 주술사에게 제조법을 속삭였다. (참고: 이 신뢰하는 친구가 그때 집에 있을 필요는 없었다. 사실, 그들이 서로의 집을 방문했을 가능성도 있다. 주술사들은 별나니까.)

다행히도 속삭임은 짧은 거리만 이동하므로, 조사관단은 (도둑과 사악한 주술사가 방문한) 두 신뢰하는 친구가 매우 가까이 살아야 한다는 것을 알고 있다.

그들은 당신에게 수사를 도와달라고 요청한다. 그들은 자신들의 의심을 시험해 보고 싶어 한다. 만약 도둑이 x이고, 사악한 주술사가 y이며, 제조법이 v일째에 속삭여졌다면 어떨까? 속삭인 제조법이 이동해야 했던 최소 거리는 얼마인가? 즉, x'가 v일째에 x의 신뢰하는 친구이고 y'가 v일째에 y의 신뢰하는 친구인 어떤 주술사 x'와 y'의 집 사이의 최소 거리(즉, min(|H**x' − H**y'|))는 얼마인가?

그들은 모든 정보를 당신과 공유한 뒤 여러 질문을 할 것이다. 당신은 다음 질문을 받기 전에 각 질문에 즉시 답해야 한다.

• 2 ≤ N ≤ 105
• 1 ≤ D ≤ 500
• 0 ≤ U ≤ 2 · 105
• 1 ≤ Q ≤ 50 000
• 모든 i에 대해 0 ≤ Hi ≤ 109 (0 ≤ i < N).
• 모든 j에 대해 0 ≤ A[j], B[j], X, Y < N이고, X ≠ Y이며 A[j] ≠ B[j]이다 (0 ≤ j < U).
• 0 ≤ V ≤ U