+ Time Limit: 1 second
+ Memory Limit: 256 megabytes
----------
In this question, we ask you to take two natural numbers from standard input and print their sum in standard output.
# Input
In the first line of input, two positive integers $a$ and $b$ separated by a space are given.
$$1 \leq a, b \leq 100$$
# Output
In the only output line, print the value of $a + b$.
# Example
## Sample Input 1
```
3 5
```
## Sample Output 1
```
8
```
## Sample Input 2
```
1 1
```
## Sample Output 2
```
2
```
+ Time Limit: 1 second
+ Memory Limit: 256 megabytes
----------
A sequence $a_1, a_2, \dots, a_n$ of integers is given to you. We ask you to write a program that sorts this sequence in ascending order and then prints it.
# Input
In the first line of input, a positive integer $n$ is given.
$$1 \leq n \leq 500,000$$
In the next line, $n$ integers separated by a space are given. The $i$-th number represents the value of $a_i$.
$$-10^9 \leq a_i \leq 10^9$$
# Output
In the only output line, there are $n$ integers separated by a space, showing the state of sequence $a$ after sorting.
# Example
## Sample Input 1
```
5
3 6 2 1 2
```
## Sample Output 1
```
1 2 2 3 6
```
## Sample Input 2
```
3
3 2 1
```
## Sample Output 2
```
1 2 3
```
## Sample Input 3
```
4
17 -22 31 19
```
## Sample Output 3
```
-22 17 19 31
```
+ Time Limit: 1 second
+ Memory Limit: 256 megabytes
----------
We have a weighted and directed graph $G$ with $n$ vertices and $m$ edges. The vertices of this graph are numbered from $1$ to $n$.
We ask you to write a program to print the shortest distance from vertex 1 to all vertices. (If there is no path from vertex 1 to a vertex, represent the distance as `-1`.)
# Input
In the first line of input, two integers $n$ and $m$ separated by a space are given, indicating the number of vertices and edges of graph $G$ respectively.
$$1 \leq n \leq 300,000$$
$$0 \leq m \leq 300,000$$
In the next $m$ lines, each line contains three integers $u$, $v$, and $w$, representing the existence of an edge from vertex $u$ to vertex $v$ with weight $w$.
$$1 \leq u, v \leq n$$
$$1 \leq w \leq 10^9$$
# Output
In one line, print the distance from vertex 1 to all vertices in order. The distance from vertex 1 to itself is 0. If there is no path from 1 to a vertex, represent the distance as `-1`.
# Example
## Sample Input 1
```
5 7
1 2 10
2 1 7
1 5 2
3 4 4
1 3 5
3 5 4
5 3 1
```
## Sample Output 1
```
0 10 3 7 2
```
## Sample Input 2
```
2 5
1 1 5
2 2 3
1 2 2
2 1 3
1 2 4
```
## Sample Output 2
```
0 2
```
+ Time Limit: 1 second
+ Memory Limit: 256 megabytes
----------
We have an array consisting of $n$ numbers. A range of these numbers is called **beautiful** if and only if the sum of the numbers in this range is less than or equal to $k$ and greater than or equal to $-k$. In other words, the absolute value of the sum of the numbers in this range must be at most $k$.
On this array, $q$ operations have been performed. Each operation is defined as follows: two numbers $i$ and $x$ are specified ($1 \le i \le n-1$), and the $i$-th element of the array is incremented by $x$, and the $i+1$-th element of the array is decremented by $x$. (Note that the value of $x$ can be negative as well.)
You are asked to calculate the number of beautiful ranges in the array once at the beginning and then after each operation.
Please note that all operations are persistent, meaning their effects remain on the array for subsequent operations.
# Input
In the first line of input, three integers $n$, $k$, and $q$ are given in order.
In the second line, $n$ numbers are given, which are the initial values of the array, denoted as $a_i$.
$$ 2 \le n \le 100,000 $$
$$ 1 \le q \le 100,000 $$
$$ 0 \le k \le 10^9$$
$$ -10^9 \le a_i, x \le 10^9$$
$$ 1 \le i \le n - 1 $$
It is also guaranteed that the **absolute value** of all array elements after each query will be at most $10^9$.
# Output
Your output should consist of $q+1$ lines, showing the number of beautiful ranges in the array before and after each operation.
# Example
## Sample Input 1
```
5 3 2
1 2 3 4 5
3 -2
2 4
```
## Sample Output 1
```
4
5
4
```
In this example, initially, the beautiful ranges are $[1]$, $[2]$, $[3]$, and $[1,2]$.
After the first operation, the array becomes: $1, 2, 1, 6, 5$. Now, the beautiful ranges are $[1]$, $[2]$, $[3]$, $[1,2]$, and $[2,3]$.
After the second operation, the array becomes: $1, 6, -3, 6, 5$. Now, the beautiful ranges are $[1]$, $[3]$, $[2,3]$, and $[3,4]$.
(Meaning of the range $[i,j]$ is a range that starts from element $i$ and continues to element $j$)
## Sample Input 2
```
5 5 5
-3 -4 0 5 -5
2 1
2 3
4 -4
2 -1
3 5
```
## Sample Output 2
```
12
12
13
12
12
13
```
## Sample Input 3
```
7 5 10
-10 11 -15 -8 6 8 8
2 -16
6 -7
2 13
2 -18
4 -6
3 -8
4 10
5 7
2 -2
6 17
```
## Sample Output 3
```
6
7
10
8
9
8
6
10
8
7
7
```