Kotori and Umi are playing games of stones, which is hosted by Honoka. The rule is the same as the classic one: There are some piles of stones and the players take turns to remove any positive number of stones from one pile. The one who can't make a legal move loses the game.

This time however, things will be a little different. As the host, Honoka will prepare the games from candidate piles of stones, where the -th pile initially has stones. Honoka will perform operations of the following two types:

1. Given three integers , and , for all change the number of stones in the -th candidate pile to , where is the current number of stones in the -th candidate pile.
2. Given three integers , and , start a game of stones consisting of piles where the -th pile contains stones for all , and the -th pile contains stones. Note that this operation is only querying for answer and will not affect the state of the candidate piles of stones.

Kotori is always the first to move. As a big fan of Kotori, you would like to know, for each game of stones, the number of ways Kotori can play in the first step to ensure her victory if both players use the best strategy. We consider two ways different if Kotori is taking stones from different piles, or from the same pile but is taking different number of stones.

输入描述:

There is only one test case in each test file.

The first line of the input contains two integers  and  () indicating the number of candidate piles and the number of operations.

The second line contains  integers  () where  indicates the initial number of stones in the -th pile.

For the following  lines, the -th line contains four integers , ,  and  (, , ) indicating the -th operation, where  is the type of operation and the others are the parameters of the operation. Operations are given in the order they're performed.

输出描述:

For each operation of the second type output one line containing one integer indicating the answer.

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

1
0
3

备注:

For the first operation the players will play a game of stones consisting of , ,  and  stone(s) in each pile respectively. The only winning play for Kotori is reduce the pile with  stones to  stone.

After the second operation, number of stones in the candidate piles changes to , , ,  and  respectively.

For the fourth operation the players will play a game of stones consisting of , , ,  and  stone(s) in each pile respectively. The winning plays for Kotori is to reduce the pile with  stone to  stone, or to reduce any pile with  stones to  stones.