Farmer Josh is raising kangaroos! There are kangaroos that are scattered on a line (with the positive end to the right), conveniently identified with integer IDs
. Each kangaroo is at an initial distinct position
, has an initial velocity of
and an acceleration of
. Every second, each kangaroo will hop to another location. To determine where the kangaroo hops, the following events happen in order:
- The kangaroo's position will increase by its velocity. More specifically,
will increase by
.
- The kangaroo's velocity will increase by its acceleration. More specifically,
will increase by
.
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, events will occur. Each event is one of the following:
1 i x y z
Kangaroomoves to position
, changes its initial velocity to
and changes its acceleration to
. In other words,
is set to
,
is set to
and
is set to
. 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 rangefrom 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
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 , please help Farmer Josh to determine the minimum number of kangaroos that he would need to move.
Constraints
All will be distinct and remain so after each event.
Subtask 1 [15%]
All kangaroos will always have an acceleration of . More specifically,
and
for each event of the first type.
Subtask 2 [25%]
All kangaroos will always have an acceleration of . More specifically,
and
for each event of the first type.
Subtask 3 [60%]
No additional constraints.
Input Specification
The first line will contain two integers and
.
The next lines contain 3 space separated integers
,
,
, representing the initial position, initial velocity and acceleration of kangaroo
respectively.
The next lines will contain one of the valid events defined above.
Output Specification
For each event of type , 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
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 starts at position
, kangaroo
starts at position
, and kangaroo
starts at position
.
For the first event of type , if the kangaroos were to begin hopping, kangaroo
would hop a distance of
to the right and arrive at position
after
second, and at position
after
seconds. Kangaroo
would hop a distance of
to the left and arrive at position
after
second, and position
after
seconds, colliding with kangaroo
. Therefore, Farmer Josh would need to move at least
kangaroo. For example, he could move kangaroo
to position
, preventing kangaroos
and
from colliding.
For the second event of type , 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.
Comments