가장 큰 수

먼 미래, 10진법에 지친 사람들은 D진법을 사용한다. 브루는 N개의 숫자 카드를 가지고 있다. 각 숫자 카드에는 0부터 D-1 사이의 수 중 하나에 대응하는 숫자가 적혀 있다.

브루의 목표는 이 숫자 카드를 적절히 배열해 가장 큰 수를 만드는 것이다.

브루는 이 놀이가 너무 지루하다고 판단해, 아래와 같이 숫자 카드의 종류를 바꿔 가면서 가장 큰 수를 만들려고 한다.

• i x: i번 카드에 적혀 있는 숫자를 x로 바꾼다. (1 ≤ i ≤ N, 0 ≤ x < D)

브루를 도와 만들 수 있는 가장 큰 수를 출력하는 프로그램을 만들어 주자.

첫 줄에 숫자 카드의 개수 N, 숫자 카드의 종류를 바꾸는 횟수 Q, 숫자의 가짓수 D가 주어진다. (1 ≤ N, Q ≤ 105, 2 ≤ D ≤ 109)

둘째 줄에 브루가 가지고 있는 숫자 카드에 적혀 있는 숫자 A1, A2, ..., AN이 주어진다. (0 ≤ Ai < D)

셋째 줄부터 Q개의 줄에는 문제 본문에서 설명한 형식으로 숫자 카드의 종류를 바꾸는 연산이 주어진다.

첫 줄에는 숫자 카드의 종류를 바꾸기 전 얻을 수 있는 가장 큰 수를 10진법으로 출력한다.

둘째 줄부터 Q개의 줄에는, 숫자 카드의 종류를 한 번 바꿀 때마다 얻을 수 있는 가장 큰 수를 10진법으로 출력한다.

답이 매우 클 수 있으므로, 109+7로 나눈 나머지를 출력하자. 만약 모든 카드에 0이 쓰여 있다면, 0을 출력한다.