Районная олимпиада по информатике 2020 года за 11 класс | Казахстанские олимпиады

Задача C. Ресторан

Ограничение по времени Ограничение по памяти
1 секунда 256 мегабайт

В ресторане есть nn официантов. Они пронумерованы от 11-го до nn. На столе стоят mm стаканов. Они пронумерованы от 11-го до mm. Изначально все стаканы пустые. Каждый официант должен налить напиток в некоторые стаканы. ii-й официант должен налить в стаканы с номерами от lil_i до rir_i по xix_i миллилитров напитка. Какой-то официант проспал и забыл сделать это. Все остальные кроме него выполнили задание. Вам дано количество миллилитров напитка в каждом стакане. Нужно найти список, тех официантов, кто возможно проспал.

Формат входного файла

В первой строке дается два целых числа nn и mm (1<=n,m<=105)(1 <= n, m <= 10^5) — количество официантов и количество стаканов. В следующих nn строках заданы по три целых числа lil_i, rir_i и xix_i (1<=li<=ri<=m(1 <= l_i <= r_i <= m, 1<=xi<=103)1 <= x_i <= 10^3). В следующей строке заданы mm целых числа a1a_1, a2a_2, \dots, ama_m, где aia_i обозначает количество миллилитров напитка в ii-м стакане.

Формат выходного файла

Выведите номера в отсортированном порядке, тех официантов, кто возможно проспал.

Примеры

Вход

5 4
1 3 2
2 4 3
1 3 2
3 4 1
3 3 1
2 5 7 4

Выход

1 3