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