Метеори#8275
Ужлянське міжзоряне співтовариство (УМС) нещодавно виявило нову планету в найближчій галактиці. На жаль, вона не підходить для колонізації через дивні метеоритні дощі, що, з іншого боку, робить цю планету дуже цікавим об'єктом для спостережень.
Держави-члени УМС вже розмістили космічні станції поблизу орбіти планети. Мета цих станцій — зібрати зразки каменів, що пролітають там. Комісія УМС поділила орбіту на секторів, пронумерованих від до (сектор і сектор є сусідніми). У кожному секторі розташована єдина космічна станція, що належить одній з держав-членів. Кожна держава повідомила кількість каменів-зразків, які вона має намір зібрати до кінця місії. Ваше завдання — для кожної держави визначити, коли вона може припинити збір зразків, базуючись на прогнозах метеоритних дощів на найближчі кілька років.
Перша стрічка стандартного вводу містить два цілих числа, і (1 \leq n, m \leq 3 \times 10^5), розділені пробілом, які позначають, відповідно, кількість держав-членів УМС і кількість секторів.
У другій стрічці наведено цілих чисел o_i (1 \leq o_i \leq n), розділених пробілами, які позначають номер держави, що володіє космічною станцією.
У третій стрічці наведено цілих чисел p_i (1 \leq p_i \leq 10^9), розділених пробілами, які позначають кількість зразків метеорів, які кожна держава має намір зібрати.
У четвертій стрічці міститься одне ціле число (1 \leq k \leq 3 \times 10^5), що означає кількість прогнозів метеоритних дощів. Наступні стрічок описують прогнози метеоритних дощів у хронологічному порядку. Кожна стрічка містить три цілі числа , , (розділені пробілами), які означають, що метеоритний дощ, як очікується, пройде в секторах l, l + 1, \ldots, r, якщо l \leq r, або в секторах l, l + 1, \ldots, m, 1, \ldots, r в іншому випадку, під час якого на кожну станцію випаде зразків метеоритів.
Ваша програма повинна вивести стрічок. -та з них повинна містити одне ціле число, що позначає кількість метеоритних дощів, після яких -та станція збере необхідну кількість зразків метеоритів, або , якщо їй це не вдасться.
Приклад 1