종욱이와 영준이는 평소 하던 1,024개의 숫자놀이가 싫증난 나머지 아무도 시도해본적이 없는 기발한  숫자 놀이를 생각해 냈다.

숫자놀이는 다음과 같고, 여기에 있는 규칙을 한 개라도 위반해선 안된다.

1.임의의 숫자들로 이루어진 리스트가 주어진다. 이때 숫자들은 중복되는 숫자들도 들어 올 수 있다. 단, 수의 범위는 1 <= A[i] <= 2,000이다.

2.리스트의 크기는 1 <= A.size() <= 20,000의 값이 주어진다.

3.숫자 놀이의 가장 핵심인 구간 정보와 임계 숫자가 주어진다.

가령 사이즈 7인 A = {1 2 5 5 5 4 4} 리스트와 입력 left = 1, right = 5, 임계 숫자 3이 주어지면, 위 숫자들의 의미하는 바는 다음과 같다.

left, right는 A의 구간 {1 2 5 5 5 4 4}를 의미하며, 임계 숫자 3은 위 구간의 숫자들 중에 3개 이상의 숫자가 있는지를 의미한다.

임게 숫자는 항상 구간의 크기의 반보다 크다. 따라서 해당 구간에 두 개의 숫자가 임계 숫자 이상 등장할 수 없다. 따라서 이 놀이에서는 임계 숫자 이상 등장하는 유일 수를 찾는 것이다. 이 예에서는 3개 이상을 차지하고 있는 숫자는 5이다. 주어진 구간에 따라 임계 숫자보다 많이 등장하는 수가 없을 수도 있다.

첫줄에는 전체 테스트 케이스  T( 1<= T <= 7)가 주어지며 그다음 줄에서부터는 다음의 규칙으로 입력이 주어진다

각 테스트 케이스의 첫번째 줄은 리스트 A를 이루는 숫자들의 갯수 S(1 <= A.size() <= 20,000)가 주어지고 그 다음 줄에는 리스트를 이루는 숫자들이 다음의 범위로(1 <=A[i] <= 2,000)  주어진다.

그 다음 줄에는 쿼리의 갯수 C(1 <= C <=10,000)가 주어진다.

그 다음 줄부터는 각각의 퀴리가 left, right, 임계숫자 순으로 주어진다.

이때 left, right의 수의 범위는 0 <= left <= right < A.size()이며,

임계 숫자는  2 * 임계숫자 >  right - left +1의 규칙을 따른다

테스트 케이스마다 각각의 범위의 임계 숫자 이상을 차지하는 숫자를 출력한다. 만약 없다면 -1를 출력한다.

이 문제는 각 테스트 케이스마다 많은 쿼리를 처리해야 하고, 각 쿼리가 같은 리스트를 이용한다는 것에 유의하세요. 쿼리의 실행속도가 빠르면 빠를 수록 좋습니다. 즉, 각 테스트 케이스의 전체 수행속도가 시간제한에 있어 중요합니다.