#include <bits/stdc++.h>
using namespace std;
const double PI = acos(-1);
const long long INF = 1LL << 62;
const long long MINF = -(1LL << 62);
template <typename T>
T getint() {
  T val = 0;
  char c;
  bool neg = false;
  while ((c = getchar()) && !(c >= '0' && c <= '9')) {
    neg |= c == '-';
  }
  do {
    val = (val * 10) + c - '0';
  } while ((c = getchar()) && (c >= '0' && c <= '9'));
  return val * (neg ? -1 : 1);
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef struct item* pitem;
struct item {
  int prior, value, cnt;
  bool rev;
  bool inv;
  pitem l, r;
};
int cnt(pitem it) { return it ? it->cnt : 0; }
void upd_cnt(pitem it) {
  if (it) it->cnt = cnt(it->l) + cnt(it->r) + 1;
}
void push(pitem it) {
  if (it && it->rev) {
    it->rev = false;
    swap(it->l, it->r);
    if (it->l) it->l->rev ^= true;
    if (it->r) it->r->rev ^= true;
  }
  if (it && it->inv) {
    it->inv = false;
    it->value = 1 - it->value;
    if (it->l) it->l->inv ^= true;
    if (it->r) it->r->inv ^= true;
  }
}
void merge(pitem& t, pitem l, pitem r) {
  push(l);
  push(r);
  if (!l || !r)
    t = l ? l : r;
  else if (l->prior > r->prior)
    merge(l->r, l->r, r), t = l;
  else
    merge(r->l, l, r->l), t = r;
  upd_cnt(t);
}
void split(pitem t, pitem& l, pitem& r, int key, int add = 0) {
  if (!t) return void(l = r = 0);
  push(t);
  int cur_key = add + cnt(t->l);
  if (key <= cur_key)
    split(t->l, l, t->l, key, add), r = t;
  else
    split(t->r, t->r, r, key, add + 1 + cnt(t->l)), l = t;
  upd_cnt(t);
}
void reverse(pitem t, int l, int r) {
  pitem t1, t2, t3;
  split(t, t1, t2, l);
  split(t2, t2, t3, r - l + 1);
  t2->rev ^= true;
  t2->inv ^= true;
  merge(t, t1, t2);
  merge(t, t, t3);
}
void output(pitem t) {
  if (!t) return;
  push(t);
  output(t->l);
  cerr << t->value << " ";
  output(t->r);
}
int at_pos(pitem& root, int x) {
  pitem t1 = NULL, t2 = NULL, t3 = NULL;
  split(root, t1, t2, x);
  split(t2, t2, t3, 1);
  int val = t2->value;
  merge(root, t1, t2);
  merge(root, root, t3);
  return val;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int T;
  cin >> T;
  while (T--) {
    int n;
    cin >> n;
    vector<int> A, B;
    string a, b;
    cin >> a >> b;
    for (auto i : a) A.push_back(i - '0');
    for (auto i : b) B.push_back(i - '0');
    pitem root = new item{uniform_int_distribution<int>(0, 2e9)(rng),
                          A[0],
                          0,
                          false,
                          false,
                          0,
                          0};
    for (int i = 1; i < (int)(A).size(); ++i) {
      pitem akt = new item{uniform_int_distribution<int>(0, 2e9)(rng),
                           A[i],
                           0,
                           false,
                           false,
                           0,
                           0};
      merge(root, root, akt);
    }
    vector<int> ans;
    for (int i = (int)(B).size() - 1; i >= 0; i--) {
      if (B[i] == (at_pos(root, 0) ^ 1)) {
        ans.push_back(i + 1);
        reverse(root, 0, i);
      } else {
        ans.push_back(1);
        reverse(root, 0, 0);
        ans.push_back(i + 1);
        reverse(root, 0, i);
      }
    }
    cout << (int)(ans).size();
    for (auto i : ans) {
      cout << " " << i;
    }
    cout << "\n";
  }
  return 0;
}

### Prompt

Your task is to create a cpp solution to the following problem:

This is the hard version of the problem. The difference between the versions is the constraint on n and the required number of operations. You can make hacks only if all versions of the problem are solved.

There are two binary strings a and b of length n (a binary string is a string consisting of symbols 0 and 1). In an operation, you select a prefix of a, and simultaneously invert the bits in the prefix (0 changes to 1 and 1 changes to 0) and reverse the order of the bits in the prefix.

For example, if a=001011 and you select the prefix of length 3, it becomes 011011. Then if you select the entire string, it becomes 001001.

Your task is to transform the string a into b in at most 2n operations. It can be proved that it is always possible.

Input

The first line contains a single integer t (1≤ t≤ 1000) — the number of test cases. Next 3t lines contain descriptions of test cases.

The first line of each test case contains a single integer n (1≤ n≤ 10^5) — the length of the binary strings.

The next two lines contain two binary strings a and b of length n.

It is guaranteed that the sum of n across all test cases does not exceed 10^5.

Output

For each test case, output an integer k (0≤ k≤ 2n), followed by k integers p_1,…,p_k (1≤ p_i≤ n). Here k is the number of operations you use and p_i is the length of the prefix you flip in the i-th operation.

Example

Input


5
2
01
10
5
01011
11100
2
01
01
10
0110011011
1000110100
1
0
1


Output


3 1 2 1
6 5 2 5 3 1 2
0
9 4 1 2 10 4 1 2 1 5
1 1

Note

In the first test case, we have 01→ 11→ 00→ 10.

In the second test case, we have 01011→ 00101→ 11101→ 01000→ 10100→ 00100→ 11100.

In the third test case, the strings are already the same. Another solution is to flip the prefix of length 2, which will leave a unchanged.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const double PI = acos(-1);
const long long INF = 1LL << 62;
const long long MINF = -(1LL << 62);
template <typename T>
T getint() {
  T val = 0;
  char c;
  bool neg = false;
  while ((c = getchar()) && !(c >= '0' && c <= '9')) {
    neg |= c == '-';
  }
  do {
    val = (val * 10) + c - '0';
  } while ((c = getchar()) && (c >= '0' && c <= '9'));
  return val * (neg ? -1 : 1);
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef struct item* pitem;
struct item {
  int prior, value, cnt;
  bool rev;
  bool inv;
  pitem l, r;
};
int cnt(pitem it) { return it ? it->cnt : 0; }
void upd_cnt(pitem it) {
  if (it) it->cnt = cnt(it->l) + cnt(it->r) + 1;
}
void push(pitem it) {
  if (it && it->rev) {
    it->rev = false;
    swap(it->l, it->r);
    if (it->l) it->l->rev ^= true;
    if (it->r) it->r->rev ^= true;
  }
  if (it && it->inv) {
    it->inv = false;
    it->value = 1 - it->value;
    if (it->l) it->l->inv ^= true;
    if (it->r) it->r->inv ^= true;
  }
}
void merge(pitem& t, pitem l, pitem r) {
  push(l);
  push(r);
  if (!l || !r)
    t = l ? l : r;
  else if (l->prior > r->prior)
    merge(l->r, l->r, r), t = l;
  else
    merge(r->l, l, r->l), t = r;
  upd_cnt(t);
}
void split(pitem t, pitem& l, pitem& r, int key, int add = 0) {
  if (!t) return void(l = r = 0);
  push(t);
  int cur_key = add + cnt(t->l);
  if (key <= cur_key)
    split(t->l, l, t->l, key, add), r = t;
  else
    split(t->r, t->r, r, key, add + 1 + cnt(t->l)), l = t;
  upd_cnt(t);
}
void reverse(pitem t, int l, int r) {
  pitem t1, t2, t3;
  split(t, t1, t2, l);
  split(t2, t2, t3, r - l + 1);
  t2->rev ^= true;
  t2->inv ^= true;
  merge(t, t1, t2);
  merge(t, t, t3);
}
void output(pitem t) {
  if (!t) return;
  push(t);
  output(t->l);
  cerr << t->value << " ";
  output(t->r);
}
int at_pos(pitem& root, int x) {
  pitem t1 = NULL, t2 = NULL, t3 = NULL;
  split(root, t1, t2, x);
  split(t2, t2, t3, 1);
  int val = t2->value;
  merge(root, t1, t2);
  merge(root, root, t3);
  return val;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int T;
  cin >> T;
  while (T--) {
    int n;
    cin >> n;
    vector<int> A, B;
    string a, b;
    cin >> a >> b;
    for (auto i : a) A.push_back(i - '0');
    for (auto i : b) B.push_back(i - '0');
    pitem root = new item{uniform_int_distribution<int>(0, 2e9)(rng),
                          A[0],
                          0,
                          false,
                          false,
                          0,
                          0};
    for (int i = 1; i < (int)(A).size(); ++i) {
      pitem akt = new item{uniform_int_distribution<int>(0, 2e9)(rng),
                           A[i],
                           0,
                           false,
                           false,
                           0,
                           0};
      merge(root, root, akt);
    }
    vector<int> ans;
    for (int i = (int)(B).size() - 1; i >= 0; i--) {
      if (B[i] == (at_pos(root, 0) ^ 1)) {
        ans.push_back(i + 1);
        reverse(root, 0, i);
      } else {
        ans.push_back(1);
        reverse(root, 0, 0);
        ans.push_back(i + 1);
        reverse(root, 0, i);
      }
    }
    cout << (int)(ans).size();
    for (auto i : ans) {
      cout << " " << i;
    }
    cout << "\n";
  }
  return 0;
}

```