Cocoly has a string $$$t$$$ of length $$$m$$$, consisting of lowercase English letters, and he would like to split it into parts. He calls a pair of strings $$$(x, y)$$$ beautiful if and only if there exists a sequence of strings $$$a_1, a_2, \ldots, a_k$$$, such that:

• $$$t = a_1 + a_2 + \ldots + a_k$$$, where $$$+$$$ denotes string concatenation.
• For each $$$1 \leq i \leq k$$$, at least one of the following holds: $$$a_i = x$$$, or $$$a_i = y$$$.

Cocoly has another string $$$s$$$ of length $$$n$$$, consisting of lowercase English letters. Now, for each $$$1 \leq i < n$$$, Cocoly wants you to determine whether the pair of strings $$$(s_1s_2 \ldots s_i, \, s_{i+1}s_{i+2} \ldots s_n)$$$ is beautiful.

Note: since the input and output are large, you may need to optimize them for this problem.

For example, in C++, it is enough to use the following lines at the start of the main() function:

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr); std::cout.tie(nullptr);
}