농부인 창호는 기르고 있는 소들이 나라에서 주최하는 장애물 뛰어넘기 대회를 준비하길 원하기 때문에, 소들은 장애물을 뛰어 넘는 연습을 하는 중이다. 너무나 연습을 많이 한 나머지 소들은 모두 지쳤고, 가능한 한 최소한의 에너지를 사용해서 장애물을 넘기를 원한다.

작은 높이의 장애물을 넘는 것은 쉽지만, 높은 높이의 장애물을 넘는 것은 장애물이 높을수록 어려워지고 그만큼 소들에게 스트레스를 준다. 따라서, 소들은 넘어야 하는 가장 높은 높이를 가진 장애물에 대해서만 생각하고자 한다.

소들의 연습방은 N(1≤N≤300)개의 위치로 이루어져 있고 각각의 위치엔 1부터 N의 숫자가 명시되어 있다. 그리고 M(1≤M≤25,000)개의 두 개의 위치사이에 대한 단방향 경로가 주어진다. 경로 또한 1부터 M으로 명시가 된다.

i번째 경로는 경로가 시작하는 위치 Si 그리고 경로의 도착 위치 Ei, 그리고 그 사이에 존재하는 장애물 Hi(1≤Hi≤1,000,000)가 주어진다. 경로 사이에는 반드시 하나의 장애물만 존재하며, 소들이 이동할 때 거치게 되는 경로에 존재하는 장애물은 반드시 넘어야 한다.

소들은 T(1≤T≤40,000)개의 연습을 마쳐야 한다. i번째의 연습은 2개의 숫자 Ai, Bi (1≤Ai, Bi≤N)로 주어지는데, 이는 소들이 Ai의 위치에서 Bi의 위치로 이동하는 연습을 해야 한다는 것이다. 소들은 Ai부터 Bi까지 뛰어 넘게 되는 최대 높이의 장애물이 최소한 낮은 높이기를 희망한다. 이를 알아보는 프로그램을 작성하라.

#1494 upload 72회 done 28회 how_to_reg 18명

소들의 장애물 넘기 timer 1초 memory 128MB

#1494

소들의 장애물 넘기 1초 128MB