Description

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$.

Input Format

• 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$.

Output Format

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

2 5 5
1001111001
2 1 2
1 2 3
2 1 2
1 3 4
2 1 2

Haru
Haru
Masuko

10 10 20
1110001000101011110100110000110111001111111110111101001111011111011101000000000111110100010000100110
2 2 1
2 9 6
2 6 10
2 1 1
2 3 2
1 7 9
2 10 10
2 10 4
1 1 7
1 8 8
1 2 3
1 2 7
2 1 9
2 6 1
1 1 3
2 10 7
1 2 4
2 9 1
1 3 7
1 1 5

Haru
Haru
Haru
Masuko
Haru
Masuko
Haru
Haru
Haru
Haru
Haru

Hint

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