Jhon is compulsive saver, he keeps a number "n" of piggy banks locked in his room.

He has a list which he wrote with a sequence of 1's and 2's that indicate the way that Jhon will deposit his money on the piggy banks. Every time Jhon gets a penny he rushes to his room and picks the 2 piggy banks who have the least amount of money, then he looks at the next number on the sequence. If that number is one (1) he deposits the penny on the piggy bank with the least amount of money. If that number is two (2) he deposits the penny on the next piggy bank with the least amount of money.

Your task is to write a program to help Jhon to determine what is the amount in the 2 piggy banks with least amount of money once the sequence is over.

If more than two have the least amount of money choose those with lowest indexes.

You can assume that n ≤ s.

Input

The input is a single data set.

n is the number of piggy banks, 2 ≤ n ≤ 10⁵

s is the sequence with 1's and 2's, 1 ≤ size(s) ≤ 10⁵

Output

A line containing what is the amount in the 2 piggy banks with least money once the sequence is over, sorted from lowest to highest.

Example

Input:
3
111112

Output:
1 2