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

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

브실이의 구슬 아이스크림

면접 대비

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

요약
색깔별 구슬 개수를 유지하면서, 각 질의마다 요청한 구슬이 모두 있으면 빼고 새 구슬을 넣는다.
난이도

보통10점 중 4점

유형
해시맵, 시뮬레이션, 구현
정답자
아직 제출이 없습니다

문제

브실이는 더위를 식히기 위해 구슬 아이스크림을 만들어 먹는다. 처음에 구슬 아이스크림에는 아이스크림 구슬이 NN개 들어 있으며, 각 구슬의 색깔은 11 이상 10910^9 이하의 정수로 표현된다.

브실이는 QQ번의 과정을 거쳐 아이스크림을 먹는다. ii번째 과정은 떠먹을 구슬의 목록 A_iA\_i와 부어 넣을 구슬의 목록 B_iB\_i로 표현된다. 브실이는 먼저 A_iA\_i에 주어진 구슬들이 현재 아이스크림에 모두 있는지 확인한다. 같은 색 구슬이 여러 번 주어지면 그 수만큼 아이스크림에 있어야 하며, 목록 A_iA\_i 가 비어있는 경우에는 아이스크림에 구슬이 모두 있는 것으로 간주한다. 만약 아이스크림에 구슬들이 모두 있다면 구슬들을 먹어 치우고 목록 B_iB\_i에 있는 구슬들을 부어 넣는다. 아이스크림에 없는 구슬이 적어도 하나 있다면 아무것도 하지 않는다.

브실이가 아이스크림을 다 먹은 후 구슬 아이스크림의 모습을 출력하자!

입력

첫 번째 줄에 처음 아이스크림의 구슬 수 NN이 주어진다. (1≤N≤200,000)(1 \le N \le 200\\,000)

두 번째 줄에 각 구슬의 색깔을 나타내는 정수 NN개가 공백으로 구분되어 주어진다.

세 번째 줄에 브실이가 아이스크림을 먹는 횟수 QQ가 주어진다. (1≤Q≤200,000)(1 \le Q \le 200\\,000)

네 번째 줄부터 QQ번의 과정에 대한 정보가 주어진다. ii번째 정보의 첫 번째 줄에는 A_iA\_i의 구슬 개수 a_ia\_i, 그리고 각 구슬의 색깔을 나타내는 a_ia\_i개의 정수가 공백으로 구분되어 주어진다. ii번째 정보의 두 번째 줄에는 B_iB\_i의 구슬 개수 b_ib\_i, 그리고 B_iB\_i의 각 구슬의 색깔을 나타내는 b_ib\_i개의 정수가 공백으로 구분되어 주어진다. (1≤i≤Q;(1 \le i \le Q; 0≤a_i,b_i≤200,000)0 \le a\_i, b\_i \le 200\\,000)

a_ia\_i의 합과 b_ib\_i의 합은 각각 200,000200\\,000 이하이다.

출력

첫 번째 줄에 아이스크림을 다 먹은 후 아이스크림의 구슬 개수 MM을 출력한다.

두 번째 줄에 아이스크림의 각 구슬의 색깔을 나타내는 MM개의 정수를 공백으로 구분하여 출력한다. M=0M = 0인 경우 두 번째 줄에 아무것도 출력하지 않는다.

각 구슬의 색깔을 어떤 순서로 출력해도 정답으로 인정된다.

예제2

  1. 예제 1

    입력
    6
    1 3 3 5 5 5
    3
    1 3
    2 4 4
    2 3 3
    1 4
    2 5 5
    1 5
    
    예상 출력
    6
    1 3 4 4 5 5
    
  2. 예제 2

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