You have a deck containing ~2N~ cards. Each card contains a unique number from ~1~ to ~2N~ on one side and cannot be identified from its other side. A friend of yours has placed your cards face down on a table such that the cards are split into two rows of ~N~ cards each and each of the rows is sorted by its number from least to greatest. You do not know the number on any of the cards.

You are bored, so you decide to play a game with these cards. Every now and then, you perform one of two operations. You either flip and reveal one of the cards or you wonder to yourself, "How many of these cards could possibly be the card with value ~v~?"

The first operation is in the form ~1\ r\ i\ v~ which indicates that the ~i^\text{th}~ card in the ~r^\text{th}~ row was flipped and the number on this card was ~v~. It is guaranteed that there will always be some configuration of cards such that it agrees with the cards shown as well as the rules in the problem statement. Also, a card will never be flipped twice.

The second operation is in the form ~2\ v~ which asks for the number of positions which could have ~v~ on the card at that position. For example, if you know that either the second card in the first row, the third card in the first row, or the third card in the second row could have that number, then the answer to the operation would be ~3~.

Constraints

~r = 1, 2~
~1 \le i \le N~
~1 \le v \le 2N~

Subtask 1 [30%]

~1 \le N \le 8~
~1 \le Q \le 25~

Subtask 2 [30%]

~1 \le N \le 1\,000~
~1 \le Q \le 10\,000~

Subtask 3 [40%]

~1 \le N \le 100\,000~
~1 \le Q \le 200\,000~

Input Specification

The first line contains two integers representing ~N~ and ~Q~.

The following ~Q~ lines contain one of the two operations in the format specified above.

Output Specification

For every one of the second operations, output the answer on a new line.

Sample Input 1

4 7
1 1 4 6
2 8
2 7
1 2 2 4
2 1
1 2 1 1
2 1

Sample Output 1

1
1
2
1

Explanation for Sample 1

After the first card is flipped, card ~8~ can only be in the last spot of the second row. This is because, as the largest value, card ~8~ must be in one of the two last spots and the last spot of the first row is already occupied by ~6~. A configuration which agrees with the information so far and also has card ~8~ in that spot is

1 2 3 6
4 5 7 8

For the next query, note that card ~7~ cannot be in the first row. Then card ~7~ can only be the second last card of the second row since card ~8~ is in the last spot and ~7~ is larger than all the other values apart from ~8~.

For the third query, card ~1~ must be in the first spot of one of the rows since it has the smallest value. It's simple to check that there do exist valid configurations where card ~1~ is in each of these spots:

1 2 5 6
3 4 7 8

and

2 3 5 6
1 4 7 8

For the final query, since card ~1~'s position has been revealed, that position is the only one which can have card ~1~.

Sample Input 2

4 13
1 1 1 1
1 1 3 7
1 1 2 4
2 3
2 1
1 2 1 2
2 3
2 7
1 2 4 6
1 2 2 3
1 2 3 5
1 1 4 8
2 3

Sample Output 2

1
1
1
1
1