# Increasing Sequence with Fixed OR

## Problem Statement

<br>

You are given a positive integer $$n$$𝑛. Find the longest sequence of positive integers $$a=\[a1,a2,…,ak]$$𝑎=\[𝑎1,𝑎2,…,𝑎𝑘] that satisfies the following conditions, and print the sequence:

* $$ai≤n$$𝑎𝑖≤𝑛 for all $$1≤i≤k$$1≤𝑖≤𝑘.
* $$a$$𝑎 is strictly increasing. That is, $$ai>ai−1$$𝑎𝑖>𝑎𝑖−1 for all $$2≤i≤k$$2≤𝑖≤𝑘.
* $$ai|ai−1=n$$𝑎𝑖|𝑎𝑖−1=𝑛 for all $$2≤i≤k$$2≤𝑖≤𝑘, where $$|$$| denotes the [bitwise OR operation](https://en.wikipedia.org/wiki/Bitwise_operation#OR).

Input

Each test contains multiple test cases. The first line contains the number of test cases $$t$$𝑡 ($$1≤t≤1000$$1≤𝑡≤1000). Description of the test cases follows.

The only line of each test case contains one integer $$n$$𝑛 ($$1≤n≤1018$$1≤𝑛≤1018).

It's guaranteed that the sum of lengths of the longest valid sequences does not exceed $$5⋅105$$5⋅105.

Output

For each testcase, print two lines. In the first line, print the length of your constructed sequence, $$k$$𝑘. In the second line, print $$k$$𝑘 positive integers, denoting the sequence. If there are multiple longest sequences, you can print any of them.

ExampleinputCopy

```
4131423
```

outputCopy

```
1
1
3
1 2 3
4
4 10 12 14
5
7 18 21 22 23
```

## Intuition

```
Check Initially

If

    // 23
    // 10111

    // 00101 5
    // 10010 18
    // 10101 21
    // 10110 22
    // 10111 23

If in 5 we put 1 initially, then we will have to put one in 18 also
Due to sum condition

So like that we generate the nums,

We get a alternating pattern 

Code is difficult refer it
```

### Links

<https://codeforces.com/contest/1988/problem/C>

### Video Links

<https://www.youtube.com/watch?v=sAUI0T6r9TA&t=1161s&ab_channel=CompetitiveProgrammingwithShayan>

### Approach 1:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
#include<bits/stdc++.h>
using namespace std;

int main(){

    int t;
    while(t--){
        int n;
        cin>>n;

        if(__builtin_popcountll(n) == 1){
            cout<<"1\n"<<n<<endl;
            continue;
        }

        int res = __builtin_popcountll(n) + 1;
        cout<<res<<endl;

    // 23
    // 10111

    // 00101 5
    // 10010 18
    // 10101 21
    // 10110 22
    // 10111 23
        for(int i=0; i<res; i++){
            int cnt = 0, cur = 0;
            int val = 0;

            for(int l = 64; l>=0; l--){
                if(n & (1ll<<l)){
                    cnt ++;
                    /*
                    Basically, Only i ones will get printed, 
                    When i = 0
                    Initial ones not printed, 
                    When i = 1, only initial one printed, then alternating because of curr
                    For zero we just ignore
                    Only at one we do alternating

                    Refer Explanation for more
                    */ 
                    
                    if(cnt <= i)
                        val += (1ll<<l);
                    else{
                        if(cur)
                            val += (1ll<<l);
                        cur = 1-cur;
                    }
                }
            }

            cout<<val<<" ";
        }  

        cout<<endl;
    }
}
```

{% endcode %}

### Approach 2:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://coding-9.gitbook.io/untitled/codechef_codeforces/bitwise/increasing-sequence-with-fixed-or.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.