F - Czarna Skrzynka

Sparing w Programowaniu Politechnika Poznańska, 10.03.2007

Zadanie F - Czarna skrzynka

Opis

Czarna Skrzynka jest prymitywną bazą danych. Może zapamiętywać liczby oraz posiada specjalną zmienną i. Początkowo Czarna Skrzynka jest pusta, a i wynosi 0. Czarna Skrzynka przetwarza sekwencję komend. Są dwa typy komend:

DODAJ(x): umieść element x w Czarnej Skrzynce.
POBIERZ: zwiększ i o 1 i zwróć i-ty minimalny element sposród wszystkich liczb znajdujących się w Czarnej Skrzynce.

Rozważmy ciąg 11 komend:

N	Komenda	i	Zawartość Czarnej Skrzynki po danej komendzie (elementy zostały posortowane)	Odpowiedź
1	DODAJ (3)	0	3
2	POBIERZ	1	3	3
3	DODAJ (1)	1	1, 3
4	POBIERZ	2	1, 3	3
5	DODAJ (-4)	2	-4, 1, 3
6	DODAJ (2)	2	-4, 1, 2, 3
7	DODAJ (9)	2	-4, 1, 2, 3, 9
9	DODAJ (-100)	2	-100, -4, 1, 2, 3, 9
9	POBIERZ	3	-100, -4, 1, 2, 3, 9	1
10	POBIERZ	4	-100, -4, 1, 2, 3, 9	2
11	DODAJ (2)	4	-100, -4, 1, 2, 2, 3, 9

Zadanie polega napisaniu programu, który implementuje Czarną Skrzynkę. Maksymalna liczba komend DODAJ i POBIERZ wynosi 30000 każdego rodzaju.

Zapiszmy ciąg komend w postaci dwóch tablic:

1. A(1), A(2), ..., A(M): ciąg elementów, które są dodawane do Czarnej skrzynki komendą DODAJ(x). Wartości tablicy A są liczbami całkowitymi, których bezwzględna wartość nie przekracza 2 000 000 000. M<=30000. Na przykład dla powyższego ciągu, mamy A=(3, 1, -4, 2, 9, -100, 2).

2. u(1), u(2), ..., u(N) : ciąg opisujący momenty wykonania komend POBIERZ. Dla powyższego przykładu wynosi on u=(1, 2, 6, 6), czyli POBIERZ jest po pierwszej, drugiej, szóstej i znów szóstej komendzie DODAJ(x).

Możesz założyć, że ciąg liczb naturalnych u(1), u(2), ..., u(N) jest posortowany niemalejąco, N<=M oraz, że dla każdego p (1<=p<=N) zachodzi p<=u(p)<=M. Wynika to z faktu, iż dla p-tego elementu naszego ciągu u pobieramy p-tą minimalną liczbę z sekwencji A(1), A(2), ..., A(u(p)).

Specyfikacja wejścia

W pierwszej linii wejścia znajduje się liczba D określająca liczbę testów. Każdy zbiór testowy zawiera kolejno: M, N, A(1), A(2), ..., A(M), u(1), u(2), ..., u(N). Wszystkie liczby są oddzielone spacjami i/lub znakami końca linii.

Specyfikacja wyjścia

W kolejnych liniach wypisz wyniki kolejnych komend POBIERZ.

Przykład

Wejście

2
1 1
2
1
7 4
3 1 -4 2 9 -100 2
1 2 6 6

Wyjście