시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
0.5 초 | 256 MB | 78 | 42 | 23 | 62.162% |
먼 미래, 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을 출력한다.
5 4 10 1 3 4 2 5 3 3 3 0 2 9 2 0
54321 53321 53210 95210 52100
2 2 1000000000 1 1 1 2 2 2
1000000001 999999994 999999995
3 2 12 1 0 0 2 1 3 1
144 156 157