$$$n$$$ trampolines are placed in a row and numbered $$$1$$$ through $$$n$$$ from left to right.
Each trampoline $$$i \ (1 \le i \le n)$$$ has a strength $$$t[i] \ (t$$$ is an array of length $$$n$$$).
If one throws a ball on trampoline $$$i$$$, it bounces immediately to the position $$$i + t[i]$$$ and the process repeats from this position to later positions (i.e., from the position $$$j = i + t[i]$$$, it bounces to position $$$j + t[j]$$$) until the ball exits the row, i.e., its position is strictly greater than $$$n$$$ for a given time.
You are given $$$q$$$ queries of two types :
The first line: you are given two space separated integers $$$n, q$$$ $$$(1 \le n, q \le 10^5)$$$.
The second line: you will be given $$$n$$$ space separated integers, the array $$$(1 \le t[i] \le 10^5)$$$.
Then $$$q$$$ queries, each query starts with $$$t \in \{0, 1 \}$$$, the type of the query.
Each query of type $$$0$$$ is described by two integers $$$i (1\le i \le n)$$$ and $$$x (1 \le x \le 10^5)$$$. Queries of type $$$1$$$ are described by one integer $$$i (1 \le i \le n)$$$ as described in the statement.
For each query of the second type, output two space separated integers : the last position the ball was in before exiting the row and the number of bounces it does before exiting the row $$$\textbf{(in this order)}$$$.
| subtask | constraints | scoring |
| $$$1$$$ | $$$1 \le n, q \le 10000$$$ | $$$5$$$ pts |
| $$$2$$$ | there are no queries of type $$$0$$$ | $$$10$$$ pts |
| $$$3$$$ | No additional constraints | $$$85$$$ pts |
3 3 1 3 2 1 1 0 1 2 1 1
2 2 3 2
Akram likes to make you suffer subarrays so he made a problem for you.
You are given an array $$$a$$$ of length $$$n$$$ we define the value of a subbarray as the difference between the maximum and the minimum value in it. We split $$$a$$$ into subarrays, find the maximum sum of values of the subarrays of $$$a$$$ amongst all possible splits.
In a split each element should be contained in one and only one subarray.
You are given $$$q$$$ queries of two types, update queries described by $$$3$$$ integers $$$l, r, x$$$ where you should increment $$$a[i]$$$ by $$$x$$$ for all $$$l\le i \le r$$$ , formally $$$\forall i \in [l, r] \ \ a[i] := a[i] + x$$$, queries of the second type require you to output the maximum sum of values if we split $$$a$$$ optimally.
In the first line two space separated integers $$$n, \ q$$$ ($$$1 \le n, q \le 10^5$$$) The second line $$$n$$$ space separated integers describing the array $$$a$$$, $$$-10^8\le a[i] \le 10^8$$$.
Then $$$q$$$ lines each of which starts with an integer $$$t (1\le t \le 2)$$$ : the type of the query, queries of type $$$1$$$ are update queries and are described by $$$3$$$ integers $$$l, r, x (1\le l \le r\le n, -10^8\le x\le 10^8)$$$. Queries of the second type require you to output the maximum sum of values if we split $$$a$$$ optimally.
For each query of the second type output the maximum sum of values if we split $$$a$$$ optimally.
| subtask | constraints | scoring |
| $$$1$$$ | the array is sorted and there are no updates | $$$5$$$ pts |
| $$$2$$$ | $$$1 \le n, q \le 200$$$ | $$$15$$$ pts |
| $$$3$$$ | $$$1 \le n, q \le 2000$$$ | $$$30$$$ pts |
| $$$4$$$ | no further constraints | $$$50$$$ pts |
4 7 -1 3 -6 8 1 4 4 2 2 1 4 4 3 2 1 1 2 -1 1 1 2 -4 2
20 23 23
You are given a tree of $$$N$$$ nodes, and an integer $$$K$$$.
Your task is to partition the leaves of the tree into $$$K$$$ groups while respecting the following:
The first line contains two integers $$$N$$$ and $$$K$$$ ($$$3 \leq N \leq 10000, 2 \leq K \leq 20$$$)
The next $$$N-1$$$ lines contain two space separated nodes representing an edge $$$u$$$ $$$v$$$ ($$$ 1 \leq u, v \leq n$$$)
A single integer, the minimal cost of a partition among all possible partitions into $$$K$$$ groups.
10 210 62 103 104 101 25 68 94 85 7
12