Сириус-12.19: 5. Декартово дерево

На вступительном экзамене по информатике в СУНЦ МГУ Вашему другу предложили реализовать структуру данных для хранения множеств чисел. Так как он специализируется на истории литературы, данную структуру придётся реализовать Вам.

Структура должна хранить m множеств чисел от 0 до n, при этом одно число может принадлежать сразу нескольким множествам.

Вы должны реализовать следующие операции на этой структуре:

• ADD e s
  Добавить в множество №s (0 <= s <= m) число e (0 <= e <= n).

• DELETE e s
  Удалить из множества №s (0 <= s <= m) число e (0 <= e <= n). Гарантируется, что до этого число e было помещено в множество

• CLEAR s
  Очистить множество №s (0 <= s <= m).

• LISTSET s
  Показать содержимое множества №s (0 <= s <= m), либо -1, если множество пусто.

• LISTSETSOF e
  Показать множества, в которых лежит число e (0 <= e <= n), либо -1, если этого числа нет ни в одном множестве.

Формат входных данных

Сначала вводятся числа N (1 <= N <= 9223372036854775807), M (1 <= M <= 100000) и K (0 <= K <= 100000) — максимальное число, номер максимального множества и количество запросов к структуре данных. Далее следуют K строк указанного формата запросов.

Формат выходных данных

На каждый запрос LISTSET Ваша программа должна вывести числа — содержимое запрошенного множества или -1, если множество пусто.

На каждый запрос LISTSETSOF Ваша программа должна вывести числа — номера множеств, содержащие запрошенное число или -1, если таких множеств не существует.

На прочие запросы не должно быть никакого вывода.

Гарантируется, что правильный вывод программы не превышает одного мегабайта.

10 10
9
ADD 1 1
ADD 1 2
ADD 2 1
LISTSET 1
LISTSETSOF 1
DELETE 1 1
LISTSET 1
CLEAR 1
LISTSET 1

1 2 
1 2 
2 
-1

10 10
5
ADD 1 1
LISTSET 10
LISTSET 1
CLEAR 1
LISTSET 1

-1
1 
-1