Suffix Range Update and Frequency Power Sum

You are given a sequence a of length \(n\), initially all zeros, and a positive integer \(k\). There will be \(q\) operations. In each operation, you are given two integers \(i\) and \(v\) which indicate that you should add \(v\) to every element of the suffix \(a_{i}, a_{i+1}, \dots, a_{n}\).

After each operation, let the frequency of an integer \(x\) in the sequence be \(f(x)\). You need to compute the sum of \(f(x)^k\) over all distinct values \(x\) in \(a\), and output the result modulo \(20051131\). Note that \(20051131\) is a prime number.

Note: Any mathematical formulas must be rendered in LaTeX format.

inputFormat

The first line contains three integers \(n\), \(k\), and \(q\) separated by spaces.

Each of the following \(q\) lines contains two integers \(i\) and \(v\), representing an operation which adds \(v\) to every element from index \(i\) to \(n\) (1-indexed).

outputFormat

After each operation, output one line containing the sum of the \(k\)th powers of the frequencies of each distinct number in the sequence, modulo \(20051131\).

sample

5 2 2
3 1
2 -1

13
17