The Cyberland Circuit Foundation consists of members. Each member has a favorite number and a unique name (the favorite numbers are not necessarily distinct).

letters have been sent between the members. Each letter has a sender and a recipient, and the content of each letter is the sender's favorite number.

Each member calculates the sum of the contents (senders' favorite numbers) they received and takes this value modulo () as his/her result number.

Your task is to determine all result numbers.

However, the situation is not as straightforward as it seems. Alice, Bob, and Circuit decide to solve this problem in a slightly more complicated way:

- Alice knows all members (name and favorite number), but knows no information about letters. She needs to send a binary string to Circuit with a length of no more than .
- Bob knows all letters (sender and recipient's name), but knows no information about members. He needs to send a binary string to Circuit with a length of no more than .
- Circuit can receive binary strings sent by Alice and Bob, and subsequently generate a binary string comprising bits as output. However, due to its limited computational power, Circuit is only capable of performing basic logical operations (e.g., AND, OR, NOT).

In the following, we will introduce how the circuit works in detail.

#### Circuit Details

The gate is the basic element of a circuit. A gate consists of zero or two boolean inputs (depending on the type of gate), and one boolean output. There are two types of gates: input gates and computation gates.

- Input gates have no input and represent the bits from binary strings
sent by Alice and Bob.
- There will be input gates, labeled from to , where and are the lengths of the strings from Alice and Bob, respectively.
- For , the output of the -th gate is the -th bit of the string from Alice.
- For , the output of the -th gate is the -th bit of the string from Bob.

- Computation gates have two inputs and represent the computation process.
- The labels for computation gates start from
- For each computation gate, you should provide labels of two dependent
gates for input, and the operation type, .
- To prevent circular dependencies, the labels of the two dependent gates must be smaller than the label of the computation gate.
- If the outputs of its two dependent gates are and respectively (), then the output of of the computation gate is:

Here are some examples that may be useful for you:

AND |
OR |
XOR |
NOT |
||
---|---|---|---|---|---|

0 | 0 | 0 | 0 | 0 | 1 |

1 | 0 | 0 | 1 | 1 | 0 |

0 | 1 | 0 | 1 | 1 | 1 |

1 | 1 | 1 | 1 | 0 | 0 |

#### Implementation Details

Please note:

- All array indices start from . For example, if is an array of length , then to are valid data, accessing indices beyond that range may cause undefined behaviour.
- All strings are terminated by a null character
`\0`

.

You should implement the following procedures:

##### Alice

```
int alice(const int n, const char names[][5], const unsigned short numbers[], bool outputs_alice[]);
```

Direction | Value | Length | Meaning | Constraint |
---|---|---|---|---|

Input | `n` |
|||

`names` |
The name of each member. | All names are distinct, consisting of lowercase English letters only, and have a maximum length of characters. | ||

`numbers` |
The favorite number of each member. | Each number is in the range from to . | ||

Output | `outputs_alice` |
The binary string sent to Circuit. | ||

(Return value) | You need to make sure that does not exceed and when is the same, must be fixed. |

##### Bob

```
int bob(const int m, const char senders[][5], const char recipients[][5], bool outputs_bob[]);
```

Direction | Value | Length | Meaning | Constraint |
---|---|---|---|---|

Input | `m` |
|||

`senders` |
The sender's name on each letter. | All names appear in Alice's input. | ||

`recipients` |
The recipient's name on each letter. | |||

Output | `outputs_bob` |
The binary string sent to Circuit. | ||

(Return value) | You need to make sure that does not exceed and when is the same, must be fixed. |

##### Circuit

To ensure that the computation process of the Circuit is like a general circuit, you cannot directly obtain the binary strings sent from Alice and Bob to Circuit. You only know the lengths of these two strings and must output the circuit structure.

```
int circuit(const int la, const int lb, int operations[], int operands[][2], int outputs_circuit[][16]);
```

Direction | Value | Length | Meaning | Constraint |
---|---|---|---|---|

Input | `la` |
|||

`lb` |
||||

Output | `operations` |
The type of operation performed by each gate in the circuit. | An integer from to . | |

`operands` |
The operands used by each gate in the circuit. | These must be less than the label of the current gate. | ||

`outputs_circuit` |
The gate label of the circuit output. | `outputs_circuit[i][j]` denotes the -th bit (counting from the least significant bit) of the final result for the -th member. The members are ordered according to Alice's input. |
||

(Return value) | , which represents the total number of gates (including input gates). | You need to ensure that . |

Although you can modify the information of gates with indices less than
in the `operations`

and `operands`

arrays, the grader would ignore such
modification.

#### Example

Consider the following calls:

```
alice(3, {"alic", "bob", "circ"}, {10000, 20000, 30000}, outputs_alice);
bob(5, {"alic", "bob", "bob", "circ", "circ"}, {"circ", "circ", "alic", "circ", "circ"}, outputs_bob);
```

It represents the following scenario:

- Alice knows there are members, the member with the name
`alic`

has a favorite number , etc. A possible output for`alice()`

is that,- The return value of
`alice()`

is , representing . - Inside the
`alice()`

function, set`outputs_alice[0] = 1`

,`outputs_alice[1] = 0`

, representing that the result binary string is`10`

.

- The return value of
- Bob knows there are letters, the first letter is from
`alic`

to`circ`

, etc. A possible output for`bob()`

is that,- The return value of
`bob()`

is , representing . - Inside the
`bob()`

function, set`outputs_bob[0] = 1`

,`outputs_bob[1] = 1`

,`outputs_bob[2] = 0`

, representing that the result binary string is`110`

.

- The return value of

Based on previous outputs for `alice()`

and `bob()`

, there will be the following call:

```
circuit(2, 3, operations, operands, outputs_circuit);
```

A correct output for this function would be

- The return value of
`circuit()`

is , meaning that we add two computation gates, labeled and . - Inside
`circuit()`

, set`operations`

,`operands`

, and`outputs_circuit`

in the following way:`operations = {-1, -1, -1, -1, -1, 8, 14}`

, where we use`-1`

to represent ignored information from input gates;`operands = {{-1, -1}, {-1, -1}, {-1, -1}, {-1, -1}, {-1, -1}, {0, 4}, {2, 5}}`

;`outputs_circuit = {{5, 5, 5, 5, 5, 6, 5, 5, 5, 6, 6, 6, 5, 5, 6, 5}, ...}`

. The array is a bit long, you can check`abc.cpp`

in the attachments for the full array.

According to the output, the computation procedure is,

- Add a type computation gate, with input from gate and gate . The output of gate is the -th bit of the string from Alice, which is . The output of gate is the -nd bit of the string from Bob, which is . So the output for gate is .
- Add a type computation gate, with input from gate and gate . The output of gate is the -th bit of the string from Bob, which is . The output of gate is . So the output for gate is .
`output_circuit[0]`

represents the final result of`alic`

, which is . Since`alic`

only receives a letter from bob, the final result of`alic`

is .- The final result of bob should be , since he receives no letter.
- The final result of
`circ`

should be .

`abc.cpp`

in the attachment can pass this example, but we do not guarantee that it can pass other test cases.

#### Constraints

For all test cases:

- m.
- All names are distinct, consisting of lowercase English letters only, and have a maximum length of characters.
- The favorite number of each member is in the range of to .
- The names of all senders and recipients appear in Alice's input array
`names`

. `alice()`

and`bob()`

have a memory limit of MiB and a time limit of seconds, respectively.`circuit()`

has a memory limit of MiB and a time limit of seconds.

**For the final evaluation, alice() and bob() may be called multiple
times in a single test case.**
The time limit of seconds is for each call.

#### Subtasks

##### Subtask Type A (12 points)

Subtasks 1, 2, 3 are subtasks of type A, where .

Each subtask has the following additional constraints:

- Subtask 1 (4 points): .
- Subtask 2 (4 points): .
- Subtask 3 (4 points): .

##### Subtask Type B (54 points)

Subtasks 4, 5, 6 are subtasks of type B, where:

- .
- There are no two letters with the same sender and recipient.
- All member names appear in Bob's input (i.e., each member either sends at least one letter or receives at least one letter).

Each subtask has the following additional constraints:

- Subtask 4 (24 points): , All members' names are single lowercase letters, and in Alice's input, they appear in order from
`a`

to`z`

. - Subtask 5 (24 points): .
- Subtask 6 (6 points): No special restrictions.

##### Subtask Type C (34 points)

Subtasks 7, 8, 9 are subtasks of type C, where .

Each subtask has the following additional constraints:

- Subtask 7 (18 points): , all members' names are two lowercase letters, and in Alice's input, they appear in
lexicographical order (
`aa`

,`ab`

,`ac`

, ,`az`

,`ba`

, ,`bz`

,`ca`

, ,`zz`

). - Subtask 8 (10 points): .
- Subtask 9 (6 points): No additional constraints.

#### Sample Grader

The sample grader reads the input in the following format:

- Line 1:
- Line :
- Line :

The sample grader outputs in the following format:

- If the program finishes successfully, the sample grader will output lines, each containing an integer, representing the final result calculated by functions you implement for each member.
- Otherwise, the grader would output nothing to stdout and prints the
error messages to the file
`abc.log`

in the directory. - Additionally, the sample grader will output values of , , and the running time of each function to
`abc.log`

.

**The sample grader will not check the memory limit and the
restriction that for the same / , / must be equal.**

#### Attachment Package

The sample grader along with sample test cases are available here: abc.zip.

## Comments

how many people got a full solve in the competition?

https://www.apio2023.org/ranking None. Max in-contest score was 66.

wow insane i didn't know; no wonder i can't solve haha. doesn't look like anyone on DMOJ has a solve either? no one i can ask about how to solve haha