Biggest Number

Time limit0.5sMemory limit256 MB

Summary

After each of Q point updates to the digits on N cards, report the largest base-D number obtainable by rearranging the cards, modulo 1e9+7.

Level: Hard8 of 10
Topics: Segment tree, Sorting, Math, Implementation
Solved: No attempts yet

Problem

In the distant future, people tired of base 10 use base D. Brew has N number cards. Each number card has a digit written on it corresponding to one of the numbers from 0 to D-1.

Brew's goal is to arrange these number cards appropriately to make the biggest number.

Brew decides this game is too boring and wants to make the biggest number while changing the digits on the cards as follows.

i x: Change the digit written on card i to x. (1 ≤ i ≤ N, 0 ≤ x < D)

Help Brew by writing a program that prints the biggest number that can be made.

Input

The first line gives the number of number cards N, the number of times the digits on the cards are changed Q, and the number of distinct digits D. (1 ≤ N, Q ≤ 105, 2 ≤ D ≤ 109)

The second line gives the digits A1, A2, ..., AN written on Brew's number cards. (0 ≤ Ai < D)

Starting from the third line, Q lines give operations that change the digits on the cards in the format described in the problem statement.

Output

The first line prints the biggest number obtainable before changing the digits on the cards, in base 10.

Starting from the second line, Q lines print the biggest number obtainable after each change to the digits on the cards, in base 10.

Since the answer can be very large, print it modulo 109+7. If every card has 0 written on it, print 0.

Examples3

Example 1

Input

Expected output

Example 2

Input

2 2 1000000000
1 1
1 2
2 2

Expected output

1000000001
999999994
999999995

Example 3
Input
```
3 2 12
1 0 0
2 1
3 1
```
Expected output
```
144
156
157
```