В душной библиотеке зарегистрировано $$$n$$$ читателей и хранятся экземпляры $$$m$$$ различных книг.
У каждого читателя есть список чтения. В нём перечислены те книги, которые читатель хочет прочитать, причём именно в том порядке, в котором они перечислены в списке. Все книги читатели берут в библиотеке на определённые сроки. Срок выдачи зависит только от количества имеющихся в наличии экземпляров выдаваемой книги: если перед выдачей в библиотеке $$$k$$$ экземпляров книги, то читатель обязан вернуть её ровно через $$$t_k$$$ дней. Другими словами, выданная в день $$$d$$$ книга сдаётся в день $$$d+t_k$$$. В день сдачи предыдущей книги читатель берёт в библиотеке следующую (если это возможно), и так далее до конца списка.
Чтобы не создавать суматохи, сдача всех книг происходит рано утром, а выдача — днём, после окончания сдачи. Если несколько читателей в один день хотят получить экземпляры одной и той же книги, то библиотека обслужит читателей в порядке возрастания их номеров. Если ни одного экземпляра нужной книги читателю не досталось (все они выданы в предыдущие дни и не возвращены, или выданы в тот же день читателям с меньшими номерами), то ожидающий книгу читатель будет ходить в библиотеку ежедневно до тех пор, пока не получит желаемое. При этом он не получает приоритета перед читателями с меньшими номерами, даже если ожидает книгу дольше их.
В первый день все экземпляры книг находятся в библиотеке, а каждый из читателей приходит за первой книгой своего списка. Для каждого читателя определите номер дня, в который он закончит читать последнюю книгу в своём списке и вернёт её в библиотеку.
В первой строке входных данных содержатся два целых числа $$$n$$$ и $$$m$$$ ($$$1 \leq n, m \leq 10^5$$$) — количество читателей и количество книг.
Во второй строке содержится $$$m$$$ целых чисел $$$c_i$$$ ($$$1 \leq c_i \leq n$$$) — количество экземпляров каждой из книг.
В третьей строке содержится $$$n$$$ целых чисел $$$t_k$$$ ($$$1 \leq t_k \leq 10^9$$$) — сроки выдачи книг, имеющихся в библиотеке в $$$k$$$ экземплярах.
Далее следуют $$$n$$$ описаний читателей, каждое из которых состоит из $$$2$$$ строк.
В первой строке каждого описания содержится целое число $$$s_i$$$ ($$$1 \leq s_i \leq m$$$) — количество книг, которые хочет прочитать читатель. Гарантируется, что сумма $$$s_i$$$ по всем читателям не превосходит $$$10^5$$$.
Во второй строке каждого описания содержится $$$s_i$$$ различных целых чисел $$$r_j$$$ ($$$1 \leq r_j \leq m$$$) — книги, которые читатель хочет прочитать.
Выведите $$$n$$$ целых чисел, по одному для каждого читателя: номер дня, в который последняя книга из списка будет сдана в библиотеку.
4 32 1 410 15 20 2522 121 231 2 321 3
21 31 46 46
В день $$$1$$$ первый читатель берёт единственный экземпляр книги номер $$$2$$$ на $$$t_1=10$$$ дней. Второй читатель берёт один из двух экземпляров книги номер $$$1$$$ на $$$t_2=15$$$ дней. Третий читатель берёт оставшийся экземпляр книги номер $$$1$$$ на $$$t_1=10$$$ дней. Четвёртому читателю книги не хватило (оба экземпляра книги номер $$$1$$$ выданы), он будет ждать.
В день $$$11$$$ первый и третий читатели возвращают соответственно книги $$$2$$$ и $$$1$$$. Теперь книгу номер $$$1$$$ ожидают $$$2$$$ читателя (первый и четвёртый), первый забирает её на $$$t_1=10$$$ дней, четвёртый продолжает ждать. Третий читатель забирает только что освободившуюся книгу номер $$$2$$$ на $$$t_1=10$$$ дней.
В день $$$16$$$ второй читатель возвращает свой экземпляр книги номер $$$1$$$. Его забирает на $$$t_1=10$$$ дней четвёртый читатель. Второй читатель хотел бы взять книгу номер $$$2$$$, но единственный экземпляр сейчас выдан третьему.
В день $$$21$$$ первый читатель возвращает книгу номер $$$1$$$ и завершает свой список, а третий читатель возвращает книгу номер $$$2$$$. Второй читатель забирает освободившуюся книгу номер $$$2$$$ на $$$t_1=10$$$ дней. Третий читатель берёт один из $$$4$$$ экземпляров книги номер $$$3$$$ на $$$t_4=25$$$ дней.
В день $$$26$$$ четвёртый читатель возвращает книгу номер $$$1$$$ и берёт один из $$$3$$$ экземпляров книги номер $$$3$$$ на $$$t_3=20$$$ дней.
В день $$$31$$$ второй читатель возвращает книгу номер $$$2$$$ и завершает свой список.
В день $$$46$$$ третий и четвёртый читатели возвращают свои экземпляры книги номер $$$3$$$ и завершают свои списки.