长度为 $N$ 的数列 $A_1, A_2, \ldots, A_N$ 给定。请编写程序执行以下查询：

• 1 i x：将 $A_i$ 改为 $x$。
• 2 l r：输出所有满足 $l \le i \le r$ 的 $A_i$ 中偶数的个数。
• 3 l r：输出所有满足 $l \le i \le r$ 的 $A_i$ 中奇数的个数。

数列的下标从 1 开始。

输入格式

第一行包含数列的长度 $N$ $(1 \le N \le 100{,}000)$。

第二行包含 $A_1, A_2, \ldots, A_N$。$(1 \le A_i \le 10^9)$

第三行包含查询的个数 $M$ $(1 \le M \le 100{,}000)$。

接下来 $M$ 行，每行包含一个查询。$(1 \le i \le N, 1 \le l \le r \le N, 1 \le x \le 10^9)$

输出格式

对于每个 2 号和 3 号查询，在一行中输出其答案。

样例

样例输入 1

6
1 2 3 4 5 6
4
2 2 5
3 1 4
1 5 4
2 1 6

样例输出 1

2
2
4