Problem: Ashu and Shanu are best buddies. One day Shanu gives Ashu a problem to test his intelligence.He gives him an array of N natural numbers and asks him to solve the following queries:-

Query 0:- modify the element present at index i to x.
Query 1:- count the number of even numbers in range l to r inclusive.
Query 2:- count the number of odd numbers in range l to r inclusive.    

input:
First line of the input contains the number N. Next line contains N natural numbers. 
Next line contains an integer Q followed by Q queries.
0 x y - modify the number at index x to y.  
1 x y - count the number of even numbers in range l to r inclusive.
2 x y - count the number of odd numbers in range l to r inclusive.  

Constraints:
1 ≤ N,Q ≤ 10^5
1 ≤ l ≤ r ≤ N  
0 ≤ Ai ≤ 10^9
1 ≤ x ≤ N
0 ≤ y ≤ 10^9

Note:- indexing starts from 1.

SAMPLE INPUT
6
1 2 3 4 5 6
4
1 2 5
2 1 4
0 5 4
1 1 6

SAMPLE OUTPUT
2
2
4

Solution (in PYTHON):

Solution:
import math


def update_tree(node, left, right, i, diff):
    tree[node][0] += diff[0]
    tree[node][1] += diff[1]

    if left == right:
        return

    mid = (left + right) / 2
    left_index = 2 * (node + 1) - 1
    right_index = 2 * (node + 1)

    if i <= mid:
        update_tree(left_index, left, mid, i, diff)
    else:
        update_tree(right_index, mid + 1, right, i, diff)


def update(i, k):
    old_val = nums[i]
    nums[i] = k

    if old_val % 2 == 0 and k % 2 == 1:
        diff = [-1, 1]
    elif old_val % 2 == 1 and k % 2 == 0:
        diff = [1, -1]
    else:
        return
    update_tree(0, 0, N - 1, i, diff)


def create_tree(node, left, right):

    if left == right:
        if nums[left] % 2 == 0:
            tree[node][0] += 1
        else:
            tree[node][1] += 1
        return

    left_index = 2 * (node + 1) - 1
    right_index = 2 * (node + 1)
    mid = (left + right) / 2
    create_tree(left_index, left, mid)
    create_tree(right_index, mid + 1, right)

    tree[node][0] = tree[left_index][0] + tree[right_index][0]
    tree[node][1] = tree[left_index][1] + tree[right_index][1]


def count(node, left, right, range):

    if range[0] == left and range[1] == right:
        return tree[node]

    mid = (left + right) / 2
    left_index = 2 * (node + 1) - 1
    right_index = 2 * (node + 1)

    if range[0] <= mid and range[1] <= mid:
        return count(left_index, left, mid, range)
    elif range[0] > mid and range[1] > mid:
        return count(right_index, mid + 1, right, range)
    else:
    #elif range[0] <= mid < range[1]:
        e1, o1 = count(left_index, left, mid, [range[0], mid])
        e2, o2 = count(right_index, mid + 1, right, [mid + 1, range[1]])
        return [e1 + e2, o1 + o2]


def preprocess(nums):
    create_tree(0, 0, N - 1)

N = input()
nums = map(int, raw_input().split())
power = math.ceil(math.log(N, 2)) + 1
length = int((2 ** power) - 1)
tree = [[0, 0] for i in range(length)]
preprocess(nums)
Q = input()

for q in range(Q):
    type, v1, v2 = map(int, raw_input().split())

    if type == 0:
        update(v1 - 1, v2)
    elif type == 1:
        print count(0, 0, N - 1, [v1 - 1, v2 - 1])[0]
    else:
        print count(0, 0, N - 1, [v1 - 1, v2 - 1])[1]