P12009 【MX-X10-T5】[LSOT-4] Masuko or Haru？

As a club activity assignment, Shion gave Yotsuba a data structure problem. Yotsuba intended to research the solution online but ended up chatting with Haru instead... With only 1 second left until 5 PM, Yotsuba had to ask Masuko for help. Masuko can solve the problem in 1 second, but now she wants to test if you can do it too!

You are given $n$ binary strings of length $m$. An **interval pair** is defined as a pair $(l, r)$ where $1 \le l \le r \le m$. An **interval set** is a collection of interval pairs. For a binary string $a$, a **transformation** with respect to an interval set $S$ involves selecting any interval pair $(l, r) \in S$ $\forall i \in [l, r]$, $a_i \gets a_i \oplus 1$ , where $\oplus$ denotes bitwise XOR. Two binary strings $a$ and $b$ are **equivalent** under an interval set $S$ if $a$ can be transformed into $b$ after any number of transformations with respect to $S$. Initially, $S = \emptyset$. There are $q$ operations, each being either an insertion or a query: - **Insertion**: Add a given interval pair $(l, r)$ to $S$. - **Query**: Given $x$ and $y$, determine whether the $x$-th and $y$-th binary strings are equivalent under the current $S$.

- The first line contains three integers $n$, $m$, $q$. - The second line contains a binary string of length $n \times m$. The $((i-1) \times m + 1)$-th to $(i \times m)$-th characters represent the $i$-th binary string. - The next $q$ lines each start with an integer $op$: - If $op = 1$, it is an insertion operation followed by two integers $l, r$. - If $op = 2$, it is a query operation followed by two integers $x, y$.

For each query, output a single line: `Masuko` if the two strings are equivalent, otherwise `Haru`.

**Sample Explanation #1** Initial binary strings are: `10011`, `11001`. - First query: $S$ is empty. The strings are obviously different. - Second query: $S = \{(2, 3)\}$. The first string can only become `10011` or `11111`, which cannot match the second string. - Third query: $S = \{(2, 3), (3, 4)\}$. Applying transformations in sequence converts the first string to the second string. Hence equivalent. **Data Range** **This problem uses subtasks with bundled testing.** - Subtask 1 (17 pts): $n, m \le 10$, $q \le 20$. - Subtask 2 (14 pts): $l = r$. - Subtask 3 (16 pts): $l = r - 1$. - Subtask 4 (13 pts): Insertions do not exceed 5000. - Subtask 5 (21 pts): All insertions occur before queries. - Subtask 6 (19 pts): No additional constraints. For all data: $1 \le q, n, m \le 5 \times 10^6$, $n \times m \le 10^7$, $1 \le l \le r \le m$, $1 \le x, y \le n$, $op \in \{1, 2\}$. Translation by DeepSeek R1