To find out if his students really understood the lecture about binary representation of integer numbers, Teacher Marcelo came up with the following problem:

“Given an integer number and a sequence of bit permutations for its binary representation, find 3 numbers: the resulting number after all permutations, the maximum and minimum values found during the permutations”.

Teacher Marcelo promised one extra point to whoever solved the problem first. Since he never did such thing before (giving extra points), you rushed to solve the problem as quick as you could, fearing the Professor could change his mind.

Input

The first line of a test case contains the integers N (0 ≤ N ≤ 2³² - 1) and K (1 ≤ K ≤ 100), representing the starting number and the number of permutations, respectively. Each of the following K lines will contain two space separated integers A and B (0 ≤ A, B ≤ 31), indicating that bits A and B must be swapped. Input ends when N = K = 0.

Output

For each test case print 3 integers separated by space: RES MAX MIN, where RES is the number N after all permutations, MIN and MAX are, respectively, the smallest and greatest intermediate value found in the permutation process. (MAX and MIN must consider the first and last value N assumed as well.)

Example 1

Input:
5 2
0 5
1 2
0 0

Output:
34 36 5