K. Formal Condition
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Given an array of integers $$$a_1, a_2, \ldots, a_n$$$ and an integer $$$k$$$. There are also $$$q$$$ queries to modify the array: replace the $$$i$$$-th element of the array $$$a$$$ with $$$x$$$.

After each query, as well as for the initial array, you need to determine the maximum value of $$$a_i + a_j$$$, where $$$1 \leq i \lt j \leq n$$$, $$$j - i \lt k$$$, and how many such pairs $$$(i, j)$$$ exist that yield the maximum value.

Note that in this problem, you need to respond to queries in "online" mode.

Input

The first line contains two numbers $$$n$$$ and $$$k$$$ ($$$2 \leq n \leq 10^5$$$, $$$2 \leq k \leq n$$$).

The second line contains $$$n$$$ numbers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$).

The third line contains a single number $$$q$$$ ($$$1 \leq q \leq 10^5$$$). Then, the following $$$q$$$ lines describe the modification queries.

For each query, two numbers $$$i$$$ and $$$x$$$ are given ($$$1 \leq i \leq n$$$, $$$1 \leq x \leq 10^9$$$), and let the answer for the previous query be $$$(mx, cnt)$$$, where $$$mx$$$ is the maximum sum and $$$cnt$$$ is how many such pairs there were. Then, you need to change the value of the element $$$((i + mx + cnt) \bmod n) + 1$$$ to the value $$$x$$$.

Output

Before all modifications and after each query, output two numbers on one line — what the maximum sum can be and how many such pairs exist.

Example
Input
5 3
5 1 1 1 5
4
1 5
4 2
1 6
3 2
Output
6 4
10 1
7 1
7 3
8 1