102692: [AtCoder]ABC269 C - Submask

Problem Statement

You are given a non-negative integer $N$. Print all non-negative integers $x$ that satisfy the following condition in ascending order.

• The set of the digit positions containing $1$ in the binary representation of $x$ is a subset of the set of the digit positions containing $1$ in the binary representation of $N$.
  • That is, the following holds for every non-negative integer $k$: if the digit in the "$2^k$s" place of $x$ is $1$, the digit in the $2^k$s place of $N$ is $1$.

Constraints

• $N$ is an integer.
• $0 \le N < 2^{60}$
• In the binary representation of $N$, at most $15$ digit positions contain $1$.

Input

The input is given from Standard Input in the following format:

$N$

Output

Print the answer as decimal integers in ascending order, each in its own line.

Sample Input 1

11

Sample Output 1

0
1
2
3
8
9
10
11

The binary representation of $N = 11_{(10)}$ is $1011_{(2)}$.
The non-negative integers $x$ that satisfy the condition are:

• $0000_{(2)}=0_{(10)}$
• $0001_{(2)}=1_{(10)}$
• $0010_{(2)}=2_{(10)}$
• $0011_{(2)}=3_{(10)}$
• $1000_{(2)}=8_{(10)}$
• $1001_{(2)}=9_{(10)}$
• $1010_{(2)}=10_{(10)}$
• $1011_{(2)}=11_{(10)}$

Sample Input 2

0

Sample Output 2

0

Sample Input 3

576461302059761664

Sample Output 3

0
524288
549755813888
549756338176
576460752303423488
576460752303947776
576461302059237376
576461302059761664

The input may not fit into a $32$-bit signed integer.

问题描述

给你一个非负整数 $N$。按升序顺序输出所有满足以下条件的非负整数 $x$。

• 二进制表示中，$x$ 的含有 1 的数位是 $N$ 的含有 1 的数位的子集。即对于每一个非负整数 $k$，如果 $x$ 的 "$2^k$ 位" 是 1，那么 $N$ 的 "$2^k$ 位" 也是 1。

限制条件

• $N$ 是一个整数。
• $0 \le N < 2^{60}$
• $N$ 的二进制表示中，最多有 $15$ 个数位含有 1。

输入

输入通过标准输入给出，格式如下：

$N$

输出

按升序顺序输出答案，每个答案占一行。

样例输入 1

11

样例输出 1

0
1
2
3
8
9
10
11

$N = 11_{(10)}$ 的二进制表示为 $1011_{(2)}$。

满足条件的非负整数 $x$ 有：

• $0000_{(2)}=0_{(10)}$
• $0001_{(2)}=1_{(10)}$
• $0010_{(2)}=2_{(10)}$
• $0011_{(2)}=3_{(10)}$
• $1000_{(2)}=8_{(10)}$
• $1001_{(2)}=9_{(10)}$
• $1010_{(2)}=10_{(10)}$
• $1011_{(2)}=11_{(10)}$

样例输入 2

0

样例输出 2

0

样例输入 3

576461302059761664

样例输出 3

0
524288
549755813888
549756338176
576460752303423488
576460752303947776
576461302059237376
576461302059761664

输入可能无法容纳在 $32$ 位有符号整数中。