Martian Coin Game

All submissions for this problem are available.

Freakin' news has recently claimed that they have discovered a civilization on mars and that they have established contact with the martians. Following is a summary of the midnight hour breakin' news on freakin' news :

Playful Configuration
A configuration of n coins placed in a 2 × n grid (2 rows, n columns) such that every column contains exactly one coin is called a playful configuration.
(Coins can only be placed inside a cell, and not on the boundary of two cells. Every coin is facing either heads-up or tails-up.)

One can update a playful configuration in the following ways :
1) switch(i, j) , where 1<=i<=j<=n :
For all integers r such that i<=r<=j, do the following :
If there is a coin at (1, r), remove it and place it, facing same side up at (2, r).
Otherwise remove the coin at (2, r) and place it, facing same side up at (1, r).
2) flip(i, j) , where 1<=i<=j<=n :
For all integers r such that i<=r<=j, do the following :
Flip the coin in column r without changing its position. (If the coin is initially facing heads-up then after flipping it will face tails-up and vice versa.)

One can query a playful configuration in the following way :
query(i, j) , where 1<=i<=j<=n :
Let h1 be the number of integers r such that i<=r<=j and there is a coin facing heads-up at (1,r).
Let h2 be the number of integers r such that i<=r<=j and there is a coin facing heads-up at (2,r).
Let t1 be the number of integers r such that i<=r<=j and there is a coin facing tails-up at (1,r).
Let t2 be the number of integers r such that i<=r<=j and there is a coin facing tails-up at (2,r).
query(i, j) returns h1,h2,t1 and t2.

The king of mars plays the following game every month :
He arranges n coins in a playful configuration. Initially all coins are in the first row (facing either heads-up or tails-up). He periodically performs operations on the configurations. Each operation is either an update (flip or switch) or a query. Any player who responds correctly to each query wins a large prize. Unfortunately, the game is too difficult and no player has yet won the coveted prize.

This month however, one of the ministers has gained access to the initial configuration as well as a list of all the operations. The minister has asked freakin' news to help him answer all queries correctly. Your job is to do this task for freakin' news.

Input Format

The first line contains a single integer n : The number of coins in the playful configuration.

The next line contains n space seperated integers f[1],f[2],...f[n] which describe the inital state of the coins. The coin in column i is initially at (1,i). If f[i] is 1, the coin at (1,i) is initially facing heads-up. Otherwise, the coin at (1,i) is initially facing tails-up.

The next line contains a single integer m : The number of operations.

The k'th of the next m lines contains 3 integers op,i,j which describe the k'th operation. Each operation is described as follows :
If op is 0, the operation is query(i,j).
If op is 1, the operation is flip(i,j).
If op is 2, the operation is switch(i,j).

Output Format

Constraints

Sample Input

Sample Output

Explanation

At the time of the first query, the configuration is :
H H H H H T T T T T
E E E E E E E E E E

At the time of the second query the configuration is :
H H E E E T T T T T
E E H H H E E E E E

At the time of the third query the configuration is :
T T E E E H H H H H
E E T T T E E E E E