{"problem":{"name":"B. Срочное сообщение","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":"CF10220B"},"statements":[{"statement_type":"Markdown","content":"В космопорте Сарка было полученно странное сообщение. Представитель Межзвездного Космоаналитического Бюро утверждал, что Флорине угрожает огромная опасность, что она в скором времени будет уничтожена, и просил разрешения на посадку в порту. Впрочем, к сообщению не отнеслись серьезно. Космоанализ — это очень сложный и запутанный раздел астрофизики, а космоаналитики зачастую отличались нестандартным образом мышления. Порой случалось, что погрузившись в работу, они теряли рассудок и нуждались в психиатрической помощи. Может быть, такое мнение о космоаналитиках — не более чем стереотип, однако было решено встретить прибывшего с каретой \"скорой помощи\".\n\nНо не каждый день встречаются сообщения о гибели целой планеты, тем более от представителей МКБ, поэтому начальник движения космопорта решил связаться с космоаналитиком и узнать, чем обосновывается его теория. Однако сделать это помешали неожиданно возникшие неполадки со связью, устранением которых следовало заняться незамедлительно.\n\nДля этого начальник космопорта решил узнать, с какой частотой может получать сообщение с корабля устройство приема. С корабля передается сообщение, закодированное двоичной строкой $s$, $s_i =$ '$0$', если в $i$-ю наносекунду приема сообщение принималось, или '$1$', если в этот момент были помехи. Гарантируется, что приемник распознал начало и конец сообщения, то есть первый и последний символы строки равны '$0$'. Начальник космопорта проводит $m$ проверок, пытаясь принимать сообщение с ограничением частоты $k_i$ — максимальным временем между приемами частей сообщения. Более формально, устройство может принимать шум, вызванный помехами, строго меньше $k_i$ наносекунд подряд, иначе сообщение не будет получено полностью. Для каждого $k_i$ начальник хочет узнать, можно ли принять все части сообщения, не испорченные помехами, соблюдая описанные условия.\n\nВ первой строке содержатся два числа $n$ и $m$ — длина сообщения и количество проверок соответственно $(2 <= n <= 10^6, 1 <= m <= 3 dot.op 10^5)$.\n\nСледующая строка содержит сообщение $s$, состоящее из нулей и единиц $(| s | = n)$.\n\nДалее следует $m$ строк, каждая содержит единственное целое число $k_i$ — ограничение частоты приема.\n\nВыведите $m$ строк, $i$-я строка содержит \"YES\" (без кавычек), если сообщение может быть принято с частотой $k_i$, и \"NO\" (без кавычек) в противном случае.\n\nВ данном примере во вторую, третью и четвертую наносекунды приемник получил помехи, таким образом ограничения частот приема $k_1 = 1$ и $k_3 = 3$ слишком малы, чтобы принять все части сообщения, в то время как ограничения $k_2 = 4$ хватает для этого.\n\n## Входные Данные\n\nВ первой строке содержатся два числа $n$ и $m$ — длина сообщения и количество проверок соответственно $(2 <= n <= 10^6, 1 <= m <= 3 dot.op 10^5)$.Следующая строка содержит сообщение $s$, состоящее из нулей и единиц $(| s | = n)$.Далее следует $m$ строк, каждая содержит единственное целое число $k_i$ — ограничение частоты приема.\n\n## Выходные Данные\n\nВыведите $m$ строк, $i$-я строка содержит \"YES\" (без кавычек), если сообщение может быть принято с частотой $k_i$, и \"NO\" (без кавычек) в противном случае.\n\n## Пример\n\nВходные данные7 3\n0111010\n1\n4\n3\nВыходные данныеNO\nYES\nNO\n\n## Примечание\n\nВ данном примере во вторую, третью и четвертую наносекунды приемник получил помехи, таким образом ограничения частот приема $k_1 = 1$ и $k_3 = 3$ слишком малы, чтобы принять все части сообщения, в то время как ограничения $k_2 = 4$ хватает для этого.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $ be the number of students.  \nLet $ G = (V, E) $ be a directed graph where $ V = \\{1, 2, \\dots, N\\} $ and $ (i, j) \\in E $ if and only if student $ i $ defeated student $ j $ (i.e., the $ j $-th character of string $ s_i $ is 'W').  \n\nLet $ d(i, j) $ denote the shortest path length (number of edges) from node $ i $ to node $ j $ in $ G $, with $ d(i, j) = 9000 $ if no such path exists, and $ d(i, i) = 0 $.  \n\nLet $ w(i) = \\max_{1 \\leq j \\leq N} d(i, j) $ be the *weakness* of student $ i $.  \n\n**Constraints**  \n- For each $ i \\in \\{1, \\dots, N\\} $, string $ s_i $ has length $ N $.  \n- $ s_{i,i} = \\text{'-'} $ for all $ i $.  \n- For all $ i \\ne j $, exactly one of $ s_{i,j} = \\text{'W'} $ and $ s_{j,i} = \\text{'L'} $ holds (i.e., exactly one directed edge exists between any distinct pair).  \n\n**Objective**  \nFind a student $ u \\in \\{1, \\dots, N\\} $ such that:  \n$$\nw(u) = \\min_{1 \\leq i \\leq N} w(i)\n$$  \nOutput $ d = w(u) $ and $ u $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10220B","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}