A. ADN
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A group of scientists is studying a special type of DNA strands. A DNA strand is represented as a string of characters A, C, G, or T. The scientists are only interested in DNA strands that have an odd number of occurrences of A.

The scientists want to identify and classify ordered pairs of DNA strands $$$(Z_1, Z_2)$$$, where $$$Z_1$$$ and $$$Z_2$$$ are DNA strands of length $$$n$$$ with an odd number of As. Note that the order of the strands matters: if $$$Z_1 \neq Z_2$$$, the pair $$$(Z_1, Z_2)$$$ is different from $$$(Z_2, Z_1)$$$. It is also possible that $$$Z_1 = Z_2$$$.

To identify the DNA pairs of length $$$n$$$, the scientists will assign each pair an identifier consisting of an ordered tuple $$$(X, Y_1, Y_2, Y_3)$$$, where $$$X$$$, $$$Y_1$$$, $$$Y_2$$$, $$$Y_3$$$ are binary strings of length $$$n$$$. $$$X$$$ is the so-called primary subidentifier, and $$$Y_1$$$, $$$Y_2$$$, and $$$Y_3$$$ are the secondary subidentifiers: therefore, the scientists impose that $$$X$$$ must be strictly greater than the maximum of $$$Y_1$$$, $$$Y_2$$$, and $$$Y_3$$$ when the binary strings are interpreted as numbers written in binary. The order of the subidentifiers also matters here.

The scientists want to design a correspondence between identifiers and pairs such that each identifier corresponds to a pair and each pair corresponds to an identifier. Help them by implementing a program that converts from identifiers to DNA strands and from DNA strands to identifiers.

You are free to establish the correspondence between identifiers of length $$$n$$$ and DNA strands of length $$$n$$$ as you wish, but the correspondence must be one-to-one: if your program prints a certain pair of DNA strands when given an identifier as input, it must print that same identifier when given that pair of DNA strands as input. And vice versa: if your program prints a certain identifier when given a pair of DNA strands as input, it must print that same pair when given that identifier as input.

Input

The input begins with a line containing an integer $$$n$$$ and a bit $$$b$$$. If $$$b = 0$$$, a line follows with four binary strings of length $$$n$$$: $$$X$$$, $$$Y_1$$$, $$$Y_2$$$, and $$$Y_3$$$. If $$$b = 1$$$, a line follows with two DNA strands of length $$$n$$$: $$$Z_1$$$ and $$$Z_2$$$.

Output

You must print one line. If $$$b = 0$$$, the line must contain two DNA strands of length $$$n$$$ separated by a space: $$$Z_1$$$ and $$$Z_2$$$. If $$$b = 1$$$, the line must contain four binary strings of length $$$n$$$ separated by spaces: $$$X$$$, $$$Y_1$$$, $$$Y_2$$$, and $$$Y_3$$$.

Interaction

This is a run-twice problem. For each test case, your program will run twice in succession independently.

If in the first execution you are asked for an identifier and you provide a pair of DNA strands, in the second execution you will be asked for that pair of strands and you must return the same original identifier (and vice versa when you are first asked for the DNA strands).

For technical reasons, you cannot assume that all input is available immediately at the start of execution; therefore, you cannot use methods that read all input at once.

Scoring
  1. (11 points) $$$n \leq 2$$$.
  2. (30 points) $$$n \leq 15$$$.
  3. (9 points) Cases with $$$b = 0$$$ will satisfy that $$$X = 2^n-1$$$ in binary; cases with $$$b = 1$$$ will correspond to what your program prints as a response to cases with $$$b = 0$$$.
  4. (10 points) Cases with $$$b = 1$$$ will satisfy that the strands do not contain any T; cases with $$$b = 0$$$ will correspond to what your program prints as a response to cases with $$$b = 1$$$.
  5. (40 points) No additional restrictions.
Examples
Input
2 0
11 01 10 10
Output
AC GA
Input
2 1
AC GA
Output
11 01 10 10
Input
1 1
A A
Output
1 0 0 0
Note
  • $$$1 \leq n \leq 2 \cdot 10^6$$$.
  • The tuples $$$(X, Y_1, Y_2, Y_3)$$$, both those provided to you and those you must print, must satisfy $$$X \gt \max (Y_1, Y_2, Y_3)$$$ interpreting the binary strings as numbers written in binary.
  • The tuples $$$(Z_1, Z_2)$$$, both those provided to you and those you must print, must satisfy that $$$Z_1$$$ and $$$Z_2$$$ are DNA strands with an odd number of occurrences of A.