Problem Background

On a dark Christmas Eve night, a giant reindeer barges in and tells our hero, "I will not leave until you solve this problem."

Problem Description

Given two positive integers \( N \) and \( M \).

You need to combine the numbers from sets \( A = \{0, 1, 2, \cdots, N-1\} \) and \( B = \{M, \cdots, M+N-1\} \) to select \( N \) ordered pairs \( (x_i, y_i) \). The requirements are:

• \( x_i \in A \), \( y_i \in B \), and \( x_i \ \& \ y_i = x_i \) (where \( \& \) denotes the bitwise AND operation).
• All \( x_i \) are distinct, and all \( y_i \) are distinct.

Input Format

Input consists of two integers \( N \) and \( M \).

Output Format

Output should contain \( N \) lines.

Each line should output two integers \( x_i \) and \( y_i \), where \( x_i \in A \) and \( y_i \in B \).

It can be proven that a valid solution always exists.

Sample Input and Output

Sample Input #1

1 3

Sample Output #1

0 3

Sample Input #2

3 5

Sample Output #2

0 7
1 5
2 6

Sample Input #3

5 10

Sample Output #3

0 12
1 13
2 10
3 11
4 14

Notes

Data Range and Constraints

For 100% of the data, \( 1 \le N \le M \), \( N+M \le 10^6 \).

Notes

This problem uses a custom Special Judge. Feel free to hack (either via private message or direct post).

The score for this problem is set according to the original COCI contest, with a maximum score of 110.

The problem is translated from COCI2019-2020 CONTEST #3 T5 Sob.

见题面 Input 部分

见题面 Output 部分