Everyone knows how to find mean, median and mode of an array of numbers. For people who don’t know this, here is the description:

• Mean is the arithmetic average of a set of values.
• Median of a finite list of numbers can be found by arranging all the observations from lowest value to highest value and picking the middle one. If there is an even number of observations, then there is no single middle value; the median is then usually defined to be the mean of the two middle values.
• The mode is the value that appears most often in a set of data. If more than one number is applicable to be the mode, select the highest value number amongst them as the mode.

The problem is just to find these 3 values. Given an array of numbers and two indices i and j, find the mean, median and mode of elements in the interval i to j including numbers at indices i and j. Note that i and j are 0 index based.

Constraints

2 <= N <= 10000
1 <= Q <= 10000
0 <= A[i] <= 10^8
0 <= i < N
i <= j < N

Input

First line contains N which is the total number of numbers in the array. The next line contains N numbers A[i] which are the elements of the array. Next line contains a number Q which defines the total number of queries we are making for the interval i to j. It is followed by Q lines each containing 2 numbers i and j which denotes the indices to be queried for.

Output

Print Q lines each containing 3 numbers Mean, Median and Mode respectively. If the answer for any case comes to be a floating point, then take the integer part of the number as the answer. For example: if mean, median and mode comes up to be 6.44 7.8 9 then the final answer is 6 7 9.

Example

Input:
5
6 5 3 7 7
2
1 2
0 4

Output:
4 4 5
5 6 7