K. Kanon
time limit per test
8 s
memory limit per test
1024 megabytes
input
standard input
output
standard output
A dream.

I'm having a long, unending dream—

a dream I've had since long, long ago,

where I gaze upon the streets through the seasons,

hoping to meet again someone who never returns,

searching for something long forgotten, even by myself.

So much time, so many years have flowed past me.

In the endless night, I have waited alone—

waiting for the final dawn that finally arrives.

—Kanon

In the following discussion, we establish the following conventions:

  • String indices start from $$$1$$$.
  • For a string $$$s$$$, $$$s[l:r]$$$ denotes the string formed by concatenating $$$s_l, s_{l+1}, \cdots, s_r$$$ in order.
  • $$$a \oplus b$$$ denotes the bitwise XOR of $$$a$$$ and $$$b$$$ in binary.
  • $$$\bigoplus\limits_{i=1}^n a_i = a_1 \oplus a_2 \oplus \cdots \oplus a_n$$$.

In Ayu's dream, there is a string $$$s$$$ of length $$$n$$$, consisting only of the digits $$$0$$$ and $$$1$$$. She needs to partition it into $$$k$$$ non-empty substrings $$$s[1:p_1], s[p_1+1:p_2], \cdots, s[p_{k-1}+1:n]$$$, where $$$1 \le p_1 \lt p_2 \lt \cdots \lt p_{k-1} \lt n$$$.

For each substring, she decides to treat its leftmost character as the most significant bit, interpreting it directly as a binary number.

Formally, if she partitions a substring $$$s[l:r]$$$, this substring is regarded as the binary representation of the decimal number $$$\sum\limits_{i=l}^r (2^{r-i} \times s_i)$$$. Leading zeros are permitted.

Ayu now defines the weight of a partitioning scheme as the bitwise XOR sum of these binary numbers. She wants to know, among all partitioning schemes, what the maximum possible weight is, and the number of schemes that achieve exactly this maximum weight.

However, Ayu has forgotten the value of $$$k$$$, so she needs the corresponding answers for each $$$k = 1, 2, \cdots, n$$$.

But she is just a little girl who struggles even with solving cubic equations, so she comes to Yuuichi—that is, you—for help.

Input

Each test contains multiple test cases.

The first line contains an integer $$$T(1 \leq T \leq 10^4)$$$, indicating the number of test cases.

For each test case, a single line is given containing a string $$$s$$$ composed solely of $$$0$$$ and $$$1$$$.

It is guaranteed that the total length of all strings in each test does not exceed $$$3 \times 10^6$$$.

Output

For each test case, to avoid excessive output, the following format is required.

(This format is for output reduction only; a correct solution works without it)

Let $$$p_1, p_2, \cdots, p_n$$$ be the maximum values (taken modulo $$$998244353$$$) for $$$k = 1, 2, \cdots, n$$$, and let $$$q_1, q_2, \cdots, q_n$$$ be the counts of schemes that achieve the maximum weight (also modulo $$$998244353$$$). Output four integers $$$A, B, C, D$$$ on a single line, separated by spaces, defined as follows:

$$$$$$ \begin{aligned} A&=\bigoplus_{i=1}^np_i\\ B&=\bigoplus_{i=1}^nq_i\\ C&=\bigoplus_{i=1}^n(p_i\times i)\\ D&=\bigoplus_{i=1}^n(q_i\times i)\\ \end{aligned} $$$$$$

Note: The modulo operation applies only to the individual $$$p_i$$$ and $$$q_i$$$ values. Do not apply modulo when computing $$$A, B, C, D$$$.

Example
Input
5
110
11010
1011010
101111011
11010101101
Output
5 2 0 6
19 3 24 9
101 4 109 30
405 7 382 33
1225 6 1144 53