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:

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

2
3
3
1
2