아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

슬라임 키우기

시간 제한2초메모리 제한1024 MB

요약
Q개의 비약을 순서대로 사용한다. 각 비약은 크기가 xi 이하인 슬라임을 yi배로 만들고, 끝난 뒤 모든 크기를 오름차순으로 출력한다.
난이도

보통10점 중 6점

유형
정렬, 이분 탐색, 구현
정답자
아직 제출이 없습니다

문제

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

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

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

입력

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

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

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

출력

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

예제2

  1. 예제 1

    입력
    2 2
0 1000000000
1 1000000000
1000000000 1000000000
    예상 출력
    0 1000000000000000000

  2. 예제 2

    입력
    6 5
1 2 3 4 5 6
3 2
4 5
10 2
23 1
8 0
    예상 출력
    10 12 12 20 20 20