시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
0.5 초 256 MB 49 22 10 62.500%

문제

먼 미래, 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을 출력한다.

예제 입력 1

5 4 10
1 3 4 2 5
3 3
3 0
2 9
2 0

예제 출력 1

54321
53321
53210
95210
52100

예제 입력 2

2 2 1000000000
1 1
1 2
2 2

예제 출력 2

1000000001
999999994
999999995

예제 입력 3

3 2 12
1 0 0
2 1
3 1

예제 출력 3

144
156
157

출처

  • 문제를 만든 사람: 79brue