题目背景

Shion 作为社团活动后的作业，给 Yotsuba 出了一道数据结构题。

Yotsuba 本来是想用水路查资料的，但是查着查着就去和 Haru 聊天了……

但是还有 1 秒就要到下午 5 点了！Yotsuba 只能去询问 Masuko 这道题怎么做了。

Masuko 当然可以在 1 秒之内解决这道题，她现在想考考你看你能不能 1 秒内解决这道题！

题目描述

给你 $n$ 个长度为 $m$ 的 01 串。

区间二元组的定义为满足 $1\le l\le r\le m$ 的二元组 $(l,r)$。

区间集合的定义为区间二元组组成的集合。

定义 01 串 $a$ 关于区间集合 $S$ 的一次变化为任选一个区间二元组 $(l,r)\in S$，$\forall i\in[l,r],a_i\gets a_i\oplus 1$（$\oplus$ 代表二进制按位异或）。

定义 01 串 $a$ 和 $b$ 在区间集合 $S$ 下等价为 $a$ 可以在经过任意次关于 $S$ 的变化后变为 $b$。

刚开始时 $S=\emptyset$。

一共有 $q$ 次操作，每次操作都为插入操作或询问操作。

插入操作为给定一个区间二元组 $(l,r)$，$S\gets S\cup \{(l,r)\}$。

询问操作为给定 $x,y$，你需要判断第 $x$ 个 01 串和第 $y$ 个 01 串是否关于区间集合 $S$ 等价。

输入格式

第一行，三个整数 $n,m,q$。

第二行，一个长为 $n\times m$ 的 01 串，每 $m$ 个字符代表一个给定的 01 串，即第 $(i-1)\times m+1$ 个字符到第 $i\times m$ 个字符表示第 $i$ 个 01 串。

接下来 $q$ 行，每行三个正整数，第一个正整数为 $op$。

• 如果 $op=1$ 代表为插入操作，接下来两个正整数为 $l,r$。
• 如果 $op=2$ 代表为询问操作，接下来两个正整数为 $x,y$。

输出格式

对于每个询问操作，输出一行，一个字符串，如果等价则输出 Masuko，否则输出 Haru。

样例

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

Haru
Haru
Masuko

样例 1 解释

每个 01 串初始形如：

10011，
11001。

• 第一次询问：此时集合 $S$ 为空。两个 01 串显然不同。
• 第二次询问：此时集合 $S$ 为 $\{(2,3)\}$，则第一个串只能变成 10011 或 11111，无法变得相同，故不等价。
• 第三次询问：此时集合 $S$ 为 $\{(2,3),(3,4)\}$，依次进行 $(2,3)$ 变换和 $(3,4)$ 变换即可变为第二个串。故等价。

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

数据范围

本题采用捆绑测试。

• 子任务 1（17 分）：$n,m\le 10$，$q\le 20$。
• 子任务 2（14 分）：$l=r$。
• 子任务 3（16 分）：$l=r-1$。
• 子任务 4（13 分）：插入操作不超过 $5000$ 次。
• 子任务 5（21 分）：所有的插入操作在所有的询问操作之前。
• 子任务 6（19 分）：无特殊性质。

对于全部的数据，$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\}$。