[IN PYTHON] In this problem, you will be dealing with a stream of integer numbers. You have to display the k th largest and kth smallest number for all the prefixes of the input stream. In simple words, after reading each number, you have to display the kth largest and kth smallest number up until that number in the stream. If the size of the stream is smaller than k then you may display the minimum for kth smallest and maximum for kth largest numbers respectively.

Input Format

The first line of input will contain the value, k. After that, each line of input will contain an integer representing the new number of the stream. The stopping point of the stream will be denoted by 0. Note that stopping point i.e., 0 will also be considered a part of the input stream.

Constraints

Size of the stream will not exceed 8000.

Output Format

Each line of the output should contain two space separated numbers, the first one representing the kth largest/maximum number and the second one representing the kth smallest/minimum number.

Sample Input 0

2 4 5 8 0 

Sample Output 0

4 4 4 5 5 5 5 4