Une séquence $A_1, A_2, \ldots, A_N$ de longueur $N$ est donnée. Écrire un programme pour exécuter les requêtes suivantes :

• 1 i x : Changer $A_i$ en $x$.
• 2 l r : Afficher le nombre de nombres pairs parmi $A_i$ tels que $l \le i \le r$.
• 3 l r : Afficher le nombre de nombres impairs parmi $A_i$ tels que $l \le i \le r$.

Les indices de la séquence commencent à 1.

Entrée

La première ligne contient la longueur $N$ de la séquence $(1 \le N \le 100\,000)$.

La deuxième ligne contient $A_1, A_2, \ldots, A_N$ $(1 \le A_i \le 10^9)$.

La troisième ligne contient le nombre de requêtes $M$ $(1 \le M \le 100\,000)$.

Les $M$ lignes suivantes contiennent chacune une requête $(1 \le i \le N$, $1 \le l \le r \le N$, $1 \le x \le 10^9)$.

Sortie

Pour chaque requête de type 2 et de type 3, afficher sa réponse sur une ligne séparée.

Exemples

Entrée 1

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

Sortie 1

2
2
4