在遥远的 OI 国，有一种选拔赛叫做省队选拔。

共有 $n$ 个人参加省队选拔，争夺省队名额。省队由 $m$ 个人组成。

第 $i$ 个人性别为 $0$（男生）或 $1$（女生），在选拔中获得分数为 $a_i$。保证所有人的分数互不相同。

确定省队名单时，首先选入分数最高的女生。如果没有女生，则忽略此步骤。然后将所有剩余的人按分数从高到低排序。从高到低依次选择，直到选出的人数达到 $m$ 为止。

你需要处理 $q$ 个查询，每个查询属于以下两种类型之一：

• 1 $a$ ($1 \le a \le n$) $b$ ($b \in \{0, 1\}$)：将第 $a$ 个人的性别修改为 $b$。
• 2 $a$ ($1 \le a \le n$)：询问第 $a$ 个人是否在省队中。如果在，输出 $1$，否则输出 $0$。

请回答每个类型为 $2$ 的查询。

输入格式

第一行包含三个整数 $n, m, q$ ($1 \le m \le n \le 10^3, 1 \le q \le 10^3$)。

接下来的 $n$ 行，每行包含两个整数 $a_i, b_i$。

接下来的 $q$ 行，每行包含两个或三个整数，具体取决于查询类型。

$1 \le a_i \le 10^9, b_i \in \{0, 1\}$

输出格式

对于每个类型为 $2$ 的查询，输出一行整数。

样例

输入 1

3 2 3
3 0
1 1
2 0
2 2
1 2 0
2 2

输出 1

1
0