25620번 - 슬라임 키우기

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

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

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

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

둘째 줄에 N개의 정수 a₁, a₂, ⋯, a_N가 공백으로 구분되어 주어진다. (0 ≤ a_i ≤ 10⁹)

셋째 줄부터 Q개의 줄에 걸쳐 x_i와 y_i가 주어진다. 구체적으로 모든 1 ≤ i ≤ N에 대해, (i + 2)번째 줄에는 x_i와 y_i가 공백으로 구분되어 주어진다. (0 ≤ x_i, y_i ≤ 10⁹)

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