Để tìm hiểu xem học sinh của mình có thực sự hiểu bài giảng về sự biểu diễn nhị phân số nguyên, giáo viên Marcelo đưa ra vấn đề sau:

"Cho một số nguyên và một chuỗi hoán vị bit cho biểu diễn nhị phân của nó, tìm 3 số: số kết quả sau tất cả các hoán vị, các giá trị cực đại và cực tiểu tìm thấy trong các hoán vị".

Giáo viên Marcelo đã hứa thêm một điểm cho bất cứ ai giải quyết vấn đề đầu tiên. Bạn cần nhanh chóng giải quyết vấn đề nhanh nhất có thể, sợ rằng Giáo sư có thể thay đổi ý định của mình.

Đầu vào

Dòng đầu tiên của một trường hợp kiểm tra chứa các số nguyên N \((0 ≤ N ≤ 2^32 - 1)\) và K (1 ≤ K ≤ 100), tương ứng với số bắt đầu và số hoán vị tương ứng. Mỗi dòng K sau đây sẽ chứa hai số nguyên A và B (0 ≤ A, B ≤ 31) cho thấy vị trí bit A và B và đổi chỗ 2 bit nay cho nhau. Đầu vào kết thúc khi N = K = 0.

Đầu ra

Đối với mỗi trường hợp thử nghiệm, in 3 số nguyên cách nhau bởi dấu cách: RES MAX MIN, trong đó RES là số N sau tất cả các hoán vị, MIN và MAX tương ứng là giá trị nhỏ nhất và lớn nhất tìm thấy trong quá trình hoán vị.

VÍ DỤ

INPUT

5 2

0 5

1 2

0 0

OUTPUT

34 36 5