해변 배구

베라는 올해 아주 열심히 일해서 동료들에게 본보기가 되었다. 3월 8일을 맞아 우수한 업무 수행에 대한 보상으로 오랫동안 기다려 온 따뜻한 나라의 휴가를 받았다. 힘든 업무의 날들은 끝났고, 베라는 지금 따뜻한 바다 해변에서 쉬고 있다.

베라가 가장 좋아하는 취미는 해변 배구다. 그녀는 이 경기의 짜릿함을 직접 누릴 날을 오랫동안 기다려 왔다. 이미 여러 명의 멋진 배구 선수와 알게 되었지만, 이 훌륭한 선수를 어느 팀이 로스터에 넣을 자격이 있는지는 아직 정하지 못했다.

N명의 팀 주장은 모두 베라를 자기 팀으로 데려오고 싶어 하므로, 각자 최대한 실력을 보이려 한다. 모두가 경기를 하고 싶어 하기 때문에 다음 규칙에 합의했다. N개의 팀이 한 줄로 선다. 첫 번째 경기는 줄의 맨 앞 두 팀이 치른다. 이긴 팀은 코트에 남고, 진 팀은 줄의 맨 뒤로 간다. 그다음 경기부터는 직전 경기의 승자가 줄의 맨 앞 팀과 붙고, 진 팀은 다시 줄의 맨 뒤로 간다. 각 팀은 고유한 힘을 가지며, 모든 팀의 힘은 서로 다르다. 경기에서는 힘이 더 센 팀이 이긴다. 경기 수는 얼마든지 많아질 수 있다.

베라는 가장 공정한 방식인 숫자 세기 노래의 원칙을 따르기로 했다. 즉 K번째 경기를 치르는 두 팀 중 한 팀에서 뛰겠다는 것이다. 그런데 나중에 보니 이미 팀을 골라 두었고, 그 선택은 힘만을 기준으로 한 것이 아니었다. 베라가 아는 숫자 세기 노래는 Q개이며, 각각 서로 다른 K 값에 대응한다. 각 K_i에 대해, 이 귀한 상을 두고 누가 싸우는지, 즉 K_i번째 경기를 치르는 두 팀이 어느 팀인지 구해야 한다.

첫 줄에 팀의 수 N이 주어진다($2 \le N \le 100000$). 둘째 줄에는 1부터 N까지의 서로 다른 N개의 수가 주어지며, 각 수는 팀의 힘을 나타낸다. 첫 번째 수는 줄 맨 앞 팀의 힘, 두 번째 수는 그다음 팀의 힘이고, 마지막 수는 줄 맨 뒤 팀의 힘이다.

셋째 줄에는 숫자 세기 노래의 개수 Q가 주어진다($1 \le Q \le 100000$). 이어서 Q개의 줄에 각각 정수 K_i가 주어진다($1 \le K_i \le 10^{18}$). K_i는 N보다 클 수 있다.

Q개의 줄을 출력한다. i번째 줄에는 K_i번째 경기를 치르는 두 팀의 힘을 출력한다. 두 수의 순서는 상관없다.