問題文

円周上に N 個の箱が並んでおり、時計回りに順に箱 1, 2, \ldots, N と番号が付けられています。 各箱には高々 1 個のボールが入っています。 最初の状態は 0, 1 からなる長さ N の文字列 S で与えられ、S_i= 1 のとき箱 i には 1 個のボールが入っており、S_i= 0 のとき箱 i にはボールが入っていません。

何個でもボールが入る台車を用いて、以下の操作を考えます。

• 箱を 1 つ選び、その箱の位置に空の台車を置く。その後、以下の手順を繰り返す。
  • 台車の位置にある箱の中のボールの有無と台車の中のボールの有無に応じて、以下のいずれかの処理を行う。
    • 箱にボールが入っているとき：箱からボールを 1 つ取り出して台車に入れる。
    • 箱が空であり、かつ台車にボールが入っているとき：台車からボールを 1 つ取り出して箱に入れる。
    • 箱も台車も空のとき：何もしない。
  • 上記の処理の後、台車にボールが入っていれば、時計回りに次の箱の位置まで台車を進める。台車にボールが入っていなければ、操作を終了する。

各 k = 1, 2, \ldots, N について、それぞれ独立に以下の問題を解いてください。

• 初期状態から始めて箱 k の位置に台車を置いたとき、台車が最終的に停止した位置にある箱の番号を求めよ。

なお、この操作において台車が必ず停止することは証明できます。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

• 1 \leq T \leq 10^5
• 2 \leq N \leq 2 \times 10^5
• S は 0, 1 からなる長さ N の文字列
• すべてのテストケースについての N の総和は 2 \times 10^5 以下
• 入力される数値はすべて整数

入力例 1

5
3
101
5
00000
2
11
6
100110
32
10110101011010101100101010110110

出力例 1

2 2 3
1 2 3 4 5
2 1
2 2 3 3 6 6
2 2 18 5 5 7 7 9 9 31 12 12 14 14 16 16 20 19 19 20 22 22 24 24 26 26 4 29 29 11 32 32

1 つ目のテストケースについて説明します。

k=1 の場合、以下のように操作が進みます。

• 箱 1 からボールを回収し、台車のボールが 1 個になる。台車は空でないので箱 2 に進む。
• 空の箱 2 へボールを 1 つ入れ、台車のボールが 0 個になる。台車が空になるため、箱 2 で停止する。

k=2 の場合、以下のように操作が進みます。

• 箱 2 も台車も空のため何も起こらず、そのまま箱 2 で停止する。

k=3 の場合、以下のように操作が進みます。

• 箱 3 からボールを回収し、台車のボールが 1 個になる。台車は空でないので箱 1 に進む。
• 箱 1 からボールを回収し、台車のボールが 2 個になる。台車は空でないので箱 2 に進む。
• 空の箱 2 へボールを 1 つ入れ、台車のボールが 1 個になる。台車は空でないので箱 3 に進む。
• 空の箱 3（最初のステップでボールを回収したため空になっている）へボールを 1 つ入れ、台車のボールが 0 個になる。台車が空になるため、箱 3 で停止する。

2 つ目のテストケースについて、すべての箱が初期状態で空です。 よって、どの箱 k から開始しても、箱も台車も空のため何も起こらず、そのまま箱 k で停止します。