Farmer Josh is raising kangaroos! There are $N$ kangaroos that are scattered on a line (with the positive end to the right), conveniently identified with integer IDs $1,2,\dots ,N$. Each kangaroo is at an initial distinct position $s_i$, has an initial velocity of $v_i$ and an acceleration of $a_i$. Every second, each kangaroo will hop to another location. To determine where the kangaroo hops, the following events happen in order:

1. The kangaroo's position will increase by its velocity. More specifically, $s_i$ will increase by $v_i$.
2. The kangaroo's velocity will increase by its acceleration. More specifically, $v_i$ will increase by $a_i$.

Note that this means neither the position nor the velocity of a kangaroo is continuously changing.

However, since the kangaroos aren't too bright, Farmer Josh is worried that the kangaroos may bump into each other. Collisions occur when more than one kangaroo hop onto the same location at the same time. Kangaroos will only collide at positive integer times.

Farmer Josh is fine with a few kangaroos colliding with each other since they will be able to recover quickly (kangaroos will continue hopping like normal after collisions), but he will be very concerned if many kangaroos collide together at the same time. So, before the kangaroos start hopping around, $Q$ events will occur. Each event is one of the following:

• 1 i x y z Kangaroo $i$ moves to position $x$, changes its initial velocity to $y$ and changes its acceleration to $z$. In other words, $s_i$ is set to $x$, $v_i$ is set to $y$ and $a_i$ is set to $z$. Note that events of this type are cumulative, i.e., this event affects all future events.

• 2 l r If all the kangaroos were to begin hopping right now, Farmer Josh would like to know the minimum number of kangaroos that need to be moved to prevent all kangaroos with IDs in the inclusive range $[l,r]$ from colliding with each other at the same time; that is, he wants to ensure that at no integer point in time do all kangaroos with IDs in the range $[l,r]$ share the same position. Farmer Josh may move any number of kangaroos to any other integral position this way, but he cannot change the velocity nor the acceleration of any kangaroo. Kangaroos cannot share initial positions with other kangaroos after being moved. Note that Farmer Josh is only asking a question, so he does not actually move any kangaroo, and no kangaroo actually hops.

For each event of type $2$, please help Farmer Josh to determine the minimum number of kangaroos that he would need to move.

Constraints

$2\le N\le {10}^5$

$1\le Q\le {10}^5$

$-{10}^8\le s_i,x\le {10}^8$

$-{10}^8\le v_i,y\le {10}^8$

$-{10}^8\le a_i,z\le {10}^8$

$1\le l<r\le N$

All $s_i$ will be distinct and remain so after each event.

Subtask 1 [15%]

$1\le N,Q\le 1000$

All kangaroos will always have an acceleration of $0$. More specifically, $a_i=0$ and $z=0$ for each event of the first type.

Subtask 2 [25%]

All kangaroos will always have an acceleration of $0$. More specifically, $a_i=0$ and $z=0$ for each event of the first type.

Subtask 3 [60%]

No additional constraints.

Input Specification

The first line will contain two integers $N$ and $Q$.

The next $N$ lines contain 3 space separated integers $s_i$, $v_i$, $a_i$, representing the initial position, initial velocity and acceleration of kangaroo $i$ respectively.

The next $Q$ lines will contain one of the valid events defined above.

Output Specification

For each event of type $2$, output a single integer representing the minimum number of kangaroos Farmer Josh would need to move to prevent all kangaroos with IDs in the inclusive range $[l,r]$ from hopping into each other at the same time.

Sample Input

3 3
-1 2 1
8 -3 2
10 8 10
2 1 2
1 2 6 2 1
2 1 3

Sample Output

1
0

Explanation

Initially, kangaroo $1$ starts at position $-1$, kangaroo $2$ starts at position $8$, and kangaroo $3$ starts at position $10$.

For the first event of type $2$, if the kangaroos were to begin hopping, kangaroo $1$ would hop a distance of $2$ to the right and arrive at position $1$ after $1$ second, and at position $4$ after $2$ seconds. Kangaroo $2$ would hop a distance of $3$ to the left and arrive at position $5$ after $1$ second, and position $4$ after $2$ seconds, colliding with kangaroo $1$. Therefore, Farmer Josh would need to move at least $1$ kangaroo. For example, he could move kangaroo $1$ to position $0$, preventing kangaroos $1$ and $2$ from colliding.

For the second event of type $2$, if the kangaroos were to begin hopping, none of the kangaroos would ever collide with each other. So, Farmer Josh would not need to move any of the kangaroos.