시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 (추가 시간 없음) 1024 MB98433846.914%

문제

N마리의 슬라임이 있다. i번째 슬라임의 크기는 ai이다.

생물학자인 레프는 슬라임의 크기를 키워주는 비약을 총 Q번, 순서대로 사용해 슬라임의 크기를 키울 것이다. 이중 i번째로 사용할 비약은 현재 크기가 xi 이하인 슬라임의 크기를 순식간에 yi배 불려내는 효과를 가지고 있다.

Q번의 비약을 차례대로 사용한 후, 슬라임들의 크기를 오름차순으로 정렬하여 나타내보자.

입력

첫째 줄에 양의 정수 NQ가 공백으로 구분되어 주어진다. (1 ≤ N, Q ≤ 200 000)

둘째 줄에 N개의 정수 a1, a2, ⋯, aN가 공백으로 구분되어 주어진다. (0 ≤ ai ≤ 109)

셋째 줄부터 Q개의 줄에 걸쳐 xiyi가 주어진다. 구체적으로 모든 1 ≤ iN에 대해, (i + 2)번째 줄에는 xiyi가 공백으로 구분되어 주어진다. (0 ≤ xi, yi ≤ 109)

출력

첫째 줄에 모든 비약을 차례대로 사용한 후 슬라임들의 크기를 오름차순으로 정렬하여, 공백으로 구분하여 출력한다.

예제 입력 1

2 2
0 1000000000
1 1000000000
1000000000 1000000000

예제 출력 1

0 1000000000000000000

예제 입력 2

6 5
1 2 3 4 5 6
3 2
4 5
10 2
23 1
8 0

예제 출력 2

10 12 12 20 20 20

출처

University > 서울대학교 > 2022 서울대학교 프로그래밍 경시대회 - Division 2 G번