eolymp
Competitions

Azerbaijan 2022: Qualifying exam in the preparation group for the International Olympiad October 29

Perfect match

You are given two integers n and m. Construct such pairs (x, y) from sets A = {0, 1, 2, ..., n1} and B = {m, ..., m + n1} so that all pairs (x, y) (xA and yB) satisfies the condition x & y = x (Here & stands for the bitwise AND operation)

Input

Two integers n and m (1nm, n + m106).

Output

Print n lines. In the line i print two integers xi and yi. xi must be in A and yi in B. Each of these pairs that you output must be a matching pair, as specified in the problem statement.

  • 0xin1 and for any ij should be xixj
  • myim + n1 and for any ij should be yiyj

Note

It can be proved that a solution always exists.

Time limit 1 second
Memory limit 128 MiB
Input example #1
3 4
Output example #1
0 4
1 5
2 6
Input example #2
6 7
Output example #2
0 8
1 9
2 10
3 11
4 12
5 7
Source Azerbaijan 2022: Qualifying exam in the preparation group for the International Olympiad October 29