Description

小X很喜欢吃苹果，有一天，他像牛顿一样坐在苹果树下休息，忽然苹果树开始掉下许多苹果。每当掉下一个苹果，小X就把它插进已经从小到大排好的一列苹果中（就像有序数列）。

但是有时候小X会提出奇怪的问题：在排好的N个苹果中，处于中位数的苹果大小是多少呢？

中位数在这里如下定义：当一列有序的苹果的个数为偶数个时，中位数是最中间的两个，否则中位数是最中间那一个。如1,2,3,4则中位数是2,3;又如1 5 7，中位数是5。

现在，你作为小X最好的朋友，请你帮助他回答他的问题。

Input

输入有不超过10组数据，第一行是组数cas，下面共有cas组数据。 每一组数据有多行，第1行是已经掉在地上的苹果数目N(N <= 100000)，第2行有N个数，表示小X已经排好序的N个苹果的大小（范围1 <= x < 2^31，已经排成不降序列）， 第3行是事件数M(M <= 10000)，从第4行到第4+M-1行是M个事件的具体内容，drop x表示掉下了一个大小为x(1 <= x < 2^31)的苹果，query表示小X询问中位数的苹果大小。

Output

针对每个query操作，输出表示中位数的苹果大小，如果是奇数个苹果的中位数则输出一个数，否则输出两个数(中间有空格，末尾无空格)。

Sample

Input

1
6
1 2 13 14 15 16
5
drop 5
drop 3
query
drop 20
query

Output

5 13
13

Source: LCS