長さ $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 から始まる。

入力

1 行目には数列の長さ $N$ が与えられる $(1 \le N \le 100{,}000)$。

2 行目には $A_1, A_2, \ldots, A_N$ が与えられる $(1 \le A_i \le 10^9)$。

3 行目にはクエリの個数 $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