Problem: Polycarp has a lot of work to do. Recently he has learned a new time management rule: "if a task takes five minutes or less, do it immediately". Polycarp likes the new rule, however he is not sure that five minutes is the optimal value. He supposes that this value d should be chosen based on existing task list.

Polycarp has a list of n tasks to complete. The i-th task has difficulty p_i, i.e. it requires exactly p_i minutes to be done. Polycarp reads the tasks one by one from the first to the n-th. If a task difficulty is d or less, Polycarp starts the work on the task immediately. If a task difficulty is strictly greater than d, he will not do the task at all. It is not allowed to rearrange tasks in the list. Polycarp doesn't spend any time for reading a task or skipping it.

Polycarp has t minutes in total to complete maximum number of tasks. But he does not want to work all the time. He decides to make a break after each group of m consecutive tasks he was working on. The break should take the same amount of time as it was spent in total on completion of these m tasks.

For example, if n=7, p=[3, 1, 4, 1, 5, 9, 2], d=3 and m=2 Polycarp works by the following schedule:

  * Polycarp reads the first task, its difficulty is not greater than d (p_1=3 ≤ d=3) and works for 3 minutes (i.e. the minutes 1, 2, 3); 
  * Polycarp reads the second task, its difficulty is not greater than d (p_2=1 ≤ d=3) and works for 1 minute (i.e. the minute 4); 
  * Polycarp notices that he has finished m=2 tasks and takes a break for 3+1=4 minutes (i.e. on the minutes 5, 6, 7, 8); 
  * Polycarp reads the third task, its difficulty is greater than d (p_3=4 > d=3) and skips it without spending any time; 
  * Polycarp reads the fourth task, its difficulty is not greater than d (p_4=1 ≤ d=3) and works for 1 minute (i.e. the minute 9); 
  * Polycarp reads the tasks 5 and 6, skips both of them (p_5>d and p_6>d); 
  * Polycarp reads the 7-th task, its difficulty is not greater than d (p_7=2 ≤ d=3) and works for 2 minutes (i.e. the minutes 10, 11); 
  * Polycarp notices that he has finished m=2 tasks and takes a break for 1+2=3 minutes (i.e. on the minutes 12, 13, 14). 



Polycarp stops exactly after t minutes. If Polycarp started a task but has not finished it by that time, the task is not considered as completed. It is allowed to complete less than m tasks in the last group. Also Polycarp considers acceptable to have shorter break than needed after the last group of tasks or even not to have this break at all — his working day is over and he will have enough time to rest anyway.

Please help Polycarp to find such value d, which would allow him to complete maximum possible number of tasks in t minutes.

Input

The first line of the input contains single integer c (1 ≤ c ≤ 5 ⋅ 10^4) — number of test cases. Then description of c test cases follows. Solve test cases separately, test cases are completely independent and do not affect each other.

Each test case is described by two lines. The first of these lines contains three space-separated integers n, m and t (1 ≤ n ≤ 2 ⋅ 10^5, 1 ≤ m ≤ 2 ⋅ 10^5, 1 ≤ t ≤ 4 ⋅ 10^{10}) — the number of tasks in Polycarp's list, the number of tasks he can do without a break and the total amount of time Polycarp can work on tasks. The second line of the test case contains n space separated integers p_1, p_2, ..., p_n (1 ≤ p_i ≤ 2 ⋅ 10^5) — difficulties of the tasks.

The sum of values n for all test cases in the input does not exceed 2 ⋅ 10^5.

Output

Print c lines, each line should contain answer for the corresponding test case — the maximum possible number of tasks Polycarp can complete and the integer value d (1 ≤ d ≤ t) Polycarp should use in time management rule, separated by space. If there are several possible values d for a test case, output any of them.

Examples

Input

4
5 2 16
5 6 1 4 7
5 3 30
5 6 1 4 7
6 4 15
12 5 15 7 20 17
1 1 50
100


Output

3 5
4 7
2 10
0 25


Input

3
11 1 29
6 4 3 7 5 3 4 7 3 5 3
7 1 5
1 1 1 1 1 1 1
5 2 18
2 3 3 7 5


Output

4 3
3 1
4 5

Note

In the first test case of the first example n=5, m=2 and t=16. The sequence of difficulties is [5, 6, 1, 4, 7]. If Polycarp chooses d=5 then he will complete 3 tasks. Polycarp will work by the following schedule:

  * Polycarp reads the first task, its difficulty is not greater than d (p_1=5 ≤ d=5) and works for 5 minutes (i.e. the minutes 1, 2, ..., 5); 
  * Polycarp reads the second task, its difficulty is greater than d (p_2=6 > d=5) and skips it without spending any time; 
  * Polycarp reads the third task, its difficulty is not greater than d (p_3=1 ≤ d=5) and works for 1 minute (i.e. the minute 6); 
  * Polycarp notices that he has finished m=2 tasks and takes a break for 5+1=6 minutes (i.e. on the minutes 7, 8, ..., 12); 
  * Polycarp reads the fourth task, its difficulty is not greater than d (p_4=4 ≤ d=5) and works for 4 minutes (i.e. the minutes 13, 14, 15, 16); 
  * Polycarp stops work because of t=16. 



In total in the first test case Polycarp will complete 3 tasks for d=5. He can't choose other value for d to increase the number of completed tasks.

Solution (in JAVA):

Solution:
import java.io.*;
import java.math.BigInteger;
import java.util.*;
/*
 * 	Roses are red
 * 		Violets are blue
 * 			I cried
 * 				And so did you
*/
public class Main
{
	public static void main(String[]args) throws Exception
	{
		int te=ni();
		while(te-->0) {
			int n=ni(),m=ni();
			long t=nl();
			int[]a=pnia(n);
			int[]b=Arrays.copyOf(a,n+1);
			Arrays.sort(b);
			int lo=0,hi=n,mid=(lo+hi+1)/2;
			while(lo<hi)
			{
				long ti=0,to=0;
				int ta=0;
				for(int i=1; i<=n; i++)
				{
					if(a[i]<=b[mid])
					{
						ti+=a[i];
						to+=a[i];
						if(ti>t)
							break;
						ta++;
						if(ta%m==0)
						{
							ti+=to;
							to=0;
						}
					}
				}
				if(ta>=mid)
					lo=mid;
				else
					hi=mid-1;
				mid=(lo+hi+1)/2;
			}
			if(mid!=0)
				pr(mid+" "+b[mid]);
			else
				pr(mid+" "+1);
		}
		System.out.println(output);
	}
	///////////////////////////////////////////
	///////////////////////////////////////////
	///template from here
//	static final long mod=998_244_353;
	static final long mod=1000_000_007;
	static final double eps=1e-7;
	static final long inf=1000_000_000_000_000_000L;
	static class pair
	{
		long a;
		int b;
		pair(){}
		pair(long c,int d){a=c;b=d;}
		@Override
		public int hashCode()
		{
			return (a+" "+b).hashCode();
		}
		public boolean equals(Object c)
		{
			return (a==(((pair)c).a)&&b==(((pair)c).b));
		}
	}
	public static void sort(int[][]a)
	{
		Arrays.sort(a, new Comparator<int[]>()
				{
			public int compare(int[]a,int[]b)
			{
				return a[0]-b[0];
			}
				});
	}
	static interface combiner
	{
		public int combine(int a, int b);
	}
	static void pr(Object a){output.append(a).append('\n');}
	static void pr(){output.append('\n');}
	static void p(Object a){output.append(a);}
	static void sop(Object a){System.out.println(a);}
	static void flush(){System.out.print(output);output=new StringBuilder();}
	static int ni(){return Integer.parseInt(in.next());}
	static long nl(){return Long.parseLong(in.next());}
	static String ns(){return in.next();}
	static double nd(){return Double.parseDouble(in.next());}
	static int[] nia(int n){int a[]=new int[n];for(int i=0; i<n; i++)a[i]=ni();return a;}
	static int[] pnia(int n){int a[]=new int[n+1];for(int i=1; i<=n; i++)a[i]=ni();return a;}
	static long[] nla(int n){long a[]=new long[n];for(int i=0; i<n; i++)a[i]=nl();return a;}
	static String[] nsa(int n){String a[]=new String[n];for(int i=0; i<n; i++)a[i]=ns();return a;}
	static double[] nda(int n){double a[]=new double[n];for(int i=0; i<n; i++)a[i]=nd();return a;}
	static Reader in=new Reader();
	static StringBuilder output=new StringBuilder();
	static Random rn=new Random();
	static void reverse(int[]a){for(int i=0; i<a.length/2; i++){a[i]^=a[a.length-i-1];a[a.length-i-1]^=a[i];a[i]^=a[a.length-i-1];}}
	static int log2n(long a)
	{
		int te=0;
		while(a>0)
		{
			a>>=1;
			++te;
		}
		return te;
	}
	static class vectorl implements Iterable<Long>
	{
		long a[];
		int size;
		vectorl(){a=new long[10];size=0;}
		vectorl(int n){a=new long[n];size=0;}
		public void add(long b){if(++size==a.length)a=Arrays.copyOf(a, 2*size);a[size-1]=b;}
		public void sort(){Arrays.sort(a, 0, size);}
		public void sort(int l, int r){Arrays.sort(a, l, r);}
		@Override
		public Iterator<Long> iterator() {
			Iterator<Long> hola=new Iterator<Long>()
					{
				int cur=0;
						@Override
						public boolean hasNext() {
							return cur<size;
						}
						@Override
						public Long next() {
							return a[cur++];
						}				
					};
			return hola;
		}
	}
	static class vector implements Iterable<Integer>
	{
		int a[],size;
		vector(){a=new int[10];}
		vector(int n){a=new int[n];}
		public void add(int b){if(++size==a.length)a=Arrays.copyOf(a, 2*size);a[size-1]=b;}
		public void sort(){Arrays.sort(a, 0, size);}
		public void sort(int l, int r){Arrays.sort(a, l, r);}
		@Override
		public Iterator<Integer> iterator() {
			Iterator<Integer> hola=new Iterator<Integer>()
					{
				int cur=0;
						@Override
						public boolean hasNext() {
							return cur<size;
						}
						@Override
						public Integer next() {
							return a[cur++];
						}				
					};
			return hola;
		}
	}
	static class deque {
		int a[];
		int head,tail;
		deque(){a=new int[8];}
		void clear()
		{
			head=0;tail=0;
		}
		void add(int i)
		{	
			head=(head+1)&(a.length-1);
			if(tail==head)
			{
				int[]b=new int[2*a.length];
				System.arraycopy(a, tail, b, 0, a.length-tail);
				System.arraycopy(a, 0, b, a.length-tail, head);
				tail=0;
				a=b;
				head=(a.length>>>1);
			}
			a[(head-1)&(a.length-1)]=i;
		}
		int poll()
		{
			tail=(tail+1)&(a.length-1);
			return a[(tail-1)&(a.length-1)];
		}
		boolean notempty()
		{
			return head!=tail;
		}
	}
	static void exit(){System.out.print(output);System.exit(0);}
	static int min(int... a){int min=a[0];for(int i:a)min=Math.min(min, i);return min;}
	static int max(int... a){int max=a[0];for(int i:a)max=Math.max(max, i);return max;}	
	static int gcd(int... a){int gcd=a[0];for(int i:a)gcd=gcd(gcd, i);return gcd;}	
	static long min(long... a){long min=a[0];for(long i:a)min=Math.min(min, i);return min;}
	static long max(long... a){long max=a[0];for(long i:a)max=Math.max(max, i);return max;}	
	static long gcd(long... a){long gcd=a[0];for(long i:a)gcd=gcd(gcd, i);return gcd;}	
	static String pr(String a, long b){String c="";while(b>0){if(b%2==1)c=c.concat(a);a=a.concat(a);b>>=1;}return c;}
	static long powm(long a, long b, long mod){long an=1;long c=a%mod;while(b>0){if(b%2==1)an=(an*c)%mod;c=(c*c)%mod;b>>=1;}return an;}
	static long powm(long a, long b){long an=1;long c=a%mod;while(b>0){if(b%2==1)an=(an*c)%mod;c=(c*c)%mod;b>>=1;}return an;}
	static long pow(long a, long b){long an=1;long c=a;while(b>0){if(b%2==1)an*=c;c*=c;b>>=1;}return an;}
	static int gcd(int a, int b){if(b==0)return a;return gcd(b, a%b);}
	static long gcd(long a, long b){if(b==0)return a;return gcd(b, a%b);}
	static class Reader{
        public BufferedReader reader;
        public StringTokenizer tokenizer;
        public Reader() {
            reader = new BufferedReader(new InputStreamReader(System.in));
            tokenizer = null;
        }
        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }
    }
}