{"problem":{"name":"E. Видеоклип","description":{"content":"Команда Макса затащила важный матч в Доту! Макс рад вдвойне, потому что он не только успешно играл, но и попутно записывал процесс игры на видео. Теперь Макс хочет увековечить свою былинную победу, см","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10096E"},"statements":[{"statement_type":"Markdown","content":"Команда Макса затащила важный матч в Доту! Макс рад вдвойне, потому что он не только успешно играл, но и попутно записывал процесс игры на видео. Теперь Макс хочет увековечить свою былинную победу, смонтировав видеоклип из самых важных моментов матча.\n\nЗапись игры Макс разделил на несколько фрагментов. Теперь он должен выбрать некоторые из этих фрагментов, чтобы, склеив их, получить видеоклип. Каждый фрагмент Макс может использовать не более одного раза; кроме того, Максу важно сохранить порядок показанных событий в первозданном виде, поэтому выбранные фрагменты в клипе должны быть упорядочены так же, как и в исходной записи. Другими словами, в качестве материала для клипа Макс должен выбрать некоторую подпоследовательность (не обязательно непрерывную) фрагментов исходной записи.\n\nРазумеется, неотъемлемой частью хорошего видеоклипа должна быть драматичная музыка. При воспроизведении клипа видеоряд и музыкальное сопровождение начинаются одновременно в момент времени 0. Максу особенно нравится, когда конец некоторого фрагмента клипа сопровождается эффектным моментом в музыкальной композиции. Макс уже выбрал подходящую фоновую музыку и составил список имеющихся в ней эффектных моментов.\n\nТеперь Макс хочет смонтировать свой видеоклип так, чтобы как можно больше раз конец фрагмента совпадал с эффектным моментом фоновой музыки. Итоговая продолжительность клипа при этом не имеет значения.\n\nПомогите Максу узнать, каким образом лучше всего смонтировать видеоклип.\n\nПервая строка содержит целое число N (1 ≤ N ≤ 3000) — количество фрагментов исходной видеозаписи.\n\nВторая строка содержит N целых чисел Li (1 ≤ Li ≤ 3000) — продолжительность каждого из фрагментов в секундах.\n\nТретья строка содержит целое число M (1 ≤ M ≤ 3000) — количество эффектных моментов в музыкальной композиции.\n\nЧетвёртая строка содержит M различных целых чисел Tj (0 < Tj ≤ 3000), упорядоченных по возрастанию, — время в секундах, когда наступает каждый из эффектных моментов.\n\nВыведите одно целое число — максимально возможное количество моментов, когда конец фрагмента клипа совпадает с эффектным моментом в музыкальной композиции.\n\n## Входные Данные\n\nПервая строка содержит целое число N (1 ≤ N ≤ 3000) — количество фрагментов исходной видеозаписи.Вторая строка содержит N целых чисел Li (1 ≤ Li ≤ 3000) — продолжительность каждого из фрагментов в секундах.Третья строка содержит целое число M (1 ≤ M ≤ 3000) — количество эффектных моментов в музыкальной композиции.Четвёртая строка содержит M различных целых чисел Tj (0 < Tj ≤ 3000), упорядоченных по возрастанию, — время в секундах, когда наступает каждый из эффектных моментов.\n\n## Выходные Данные\n\nВыведите одно целое число — максимально возможное количество моментов, когда конец фрагмента клипа совпадает с эффектным моментом в музыкальной композиции.\n\n## Примеры\n\nВходные данные81 2 5 5 1 6 4 262 4 6 7 9 10Выходные данные3Входные данные82 6 1 8 2 5 4 172 5 6 7 8 9 10Выходные данные4\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n = 2^k $.  \nLet $ \\pi : \\{0, 1, \\dots, n-1\\} \\to \\{0, 1, \\dots, n-1\\} $ be the permutation induced by recursively folding the strip of $ n $ cells in half (right over left) until length 1, where $ \\pi(i) $ is the final top-to-bottom position of the cell originally at index $ i $.  \n\nLet $ F(l, r) = \\sum_{i=l}^{r} (-1)^{i-l} \\cdot \\pi(i) $.  \n\nLet $ m \\in \\mathbb{Z}^+ $, $ l_0, r_0 \\in \\{0, \\dots, n-1\\} $, $ a, b, c \\in \\mathbb{Z} $ be given.  \nDefine sequence of queries $ (l_j, r_j) $ for $ j = 0, \\dots, m-1 $:  \n$$\nl_j = (l_{j-1} + a \\cdot h_{j-1} + b) \\bmod n, \\quad\nr_j = (r_{j-1} + a \\cdot h_{j-1} + c) \\bmod n, \\quad \\text{for } j \\geq 1\n$$  \nwith $ h_0 = 0 $, and $ h_j = h_{j-1} \\oplus F(l_j, r_j) $ for $ j \\geq 1 $.  \n\n**Constraints**  \n1. $ 0 \\leq k \\leq 30 $ → $ n = 2^k \\leq 2^{30} $  \n2. $ 1 \\leq m \\leq 10^7 $  \n3. $ 0 \\leq l_0 \\leq r_0 < n $  \n4. $ 0 \\leq a, b, c < 2^{30} $  \n\n**Objective**  \nCompute $ h_m $, the final hash value after $ m $ queries.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10096E","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}