{"raw_statement":[{"iden":"statement","content":"Поиски книг о космическом анализе привлекли много внимания, и двое патрульных попытались задержать Рика и Мирлина Теренса. К счастью, на помощь к ним пришла Валлона, и, оглушив нейрохлыстом патрульных, наши герои сбежали обратно в Нижний город. Незамедлительно за ними был выслан целый отряд патрульных, но в Нижнем городе нашелся человек, котрый был готов спрятать беглецов от патрульных. Транторианский агент Матт Хоров укрыл Рика и Валлону в своей пекарне, а Теренс тем временем отправился домой — отсутствие резидента в течение дня могли заметить, а привлекать лишнее внимание Теренс не хотел.\n\nНа следующее утро Матт решил отправить Рика и Валлону с Флорины, где им угрожала опасность, на какую-нибудь другую планету. Хоров выдал им поддельные паспорта и билеты на корабль до Вотекса, но оставалась нерешенная проблема — огромное количество патрульных в Верхнем городе. Но Матт Хоров мог использовать других агентов, чтобы доставить Рика и Валлону в космопорт.\n\nЧтобы не привлекать излишнего внимания, Матт решил, что поднимутся они не у самого космопорта, а в каком-либо из $8$ кварталов Верхнего города, затем проедут по некоторым из этих кварталов, вероятно, не по одному разу, а затем из последнего посещенного квартала отправятся прямо в космопорт. Сопровождать Рика и Валлону будут некоторые из $n$ агентов Хорова. Для каждого агента известно, из каких кварталов в какие он может перемещаться. Путешествие проходит следующим образом: Рик с Валлоной поднимаются в одном из кварталов, где их встречает первый агент. За один доступный ему переезд он добирается до некоторого следующего квартала, где его ждет второй агент, который везет их до следующего квартала, и так далее до последнего квартала перед космопортом.\n\nЧтобы сбежать от возможной погони, Матт хочет рассмотреть разные маршруты. Он уже придумал $m$ планов, каждый состоит из стартового квартала $s_i$, конечного квартала $t_i$, а также чисел $l_i$ и $r_i$ — Рика и Валлону будут сопровождать агенты с $l_i$-го по $r_i$-го включительно, в порядке следования их номеров. Таким образом, в квартале $s_i$ их встречает $l_i$ агент и перемещается с ними в некоторый следующий квартал, где их поджидает $l_{i + 1}$ агент, который помогает им переместиться в другой квартал, и так далее. Наконец $r_i$ агент должен доставить Рика и Валлону в квартал $t_i$. При этом Матт выбирал агентов обдуманно, по этому никакой из отрезков $[ l_i \\; r_i ]$ не вложен в другой. Формально, не существует таких $i$ и $j$, таких что $l_i < l_j <= r_j < r_i$.\n\nДля каждого из планов Матт хочет узнать число различных путей, которыми данные агенты могут доставить из стартового квартала в конечный, по модулю $998244353$. Пути считаются различными, если существует номер $l <= k <= r$, такой что после поездки с $k$-м агентом по этим путям Рик с Валлоной добрались бы до разных кварталов. Обратите внимание, что для запутывания следов они могут посещать один квартал несколько раз, в том числе подряд.\n\nВ первой строке содержатся целые числа $n$ и $m$ — число агентов и число запросов соответственно $(1 <= n <= 10^5, 1 <= m <= 2 dot.op 10^5)$.\n\nВ следующих $n$ строках заданы целые числа от $0$ до $2^(64) -1$, задающие бинарные матрицы $8 times 8$ перемещения агентов. Матрица получается следующим образом: число записывается в двоичной системе счисления, дополняется ведущими нулями до 64 знаков, после чего его цифры слева направо записываются как элементы матрицы. Заполнение идет по строкам слева направо, начиная с верхней и заканчивая нижней. В полученной матрице элемент $i$-й строки $j$-го столбца $a_{i j} = 1$, если и только если соответствующий агент может проехать от $i$-го квартала до $j$-го.\n\nДалее идут $m$ строк, по четыре числа в каждой: $l_i, r_i$ - номера первого и последнего агентов, затем $s_i, t_i$ - номера стартового и конечного кварталов $(1 <= l_i <= r_i <= n \\; 1 <= s_i, t_i <= 8)$.\n\nВыведите $m$ строк, в $i$-й строке — ответ на $i$-й запрос по модулю $998244353$.\n\nПереведем данные числа в двоичную систему счисления, дополнив ведущими нулями при необходимости. Получим следующий результат: \n\n$9241386504218214000_{10} = 1000000001000000000000000001000000001000000001000000001000000001_2,$\n\n$4692768438333080000_{10} = 0100000100100000000100000000100000000100000000100000000110000000_2$,\n\n$4620710844295152000_{10} = 0100000000100000000100000000100000000100000000100000000110000000_2$.\n\nТеперь составим из полученных чисел матрицы $8 times 8$:\n\nВ первом запросе необходимо попасть из третьего квартала в четвертый, используя помощь первого и второго агентов. Но первый агент не может переместиться никуда из третьего квартала. Таким образом осуществить побег не удастся.\n\nВо втором запросе нужно попасть из первого квартала в третий, используя помощь первого, второго и третьего агентов. Возможный маршрут лишь один: $1 arrow.r 2 arrow.r 3$.\n\nВ третьем запросе требуется попасть из первого квартала во второй с помощью третьего агента. Это можно сделать ровно одним способом.\n\n"},{"iden":"входные данные","content":"В первой строке содержатся целые числа $n$ и $m$ — число агентов и число запросов соответственно $(1 <= n <= 10^5, 1 <= m <= 2 dot.op 10^5)$.В следующих $n$ строках заданы целые числа от $0$ до $2^(64) -1$, задающие бинарные матрицы $8 times 8$ перемещения агентов. Матрица получается следующим образом: число записывается в двоичной системе счисления, дополняется ведущими нулями до 64 знаков, после чего его цифры слева направо записываются как элементы матрицы. Заполнение идет по строкам слева направо, начиная с верхней и заканчивая нижней. В полученной матрице элемент $i$-й строки $j$-го столбца $a_{i j} = 1$, если и только если соответствующий агент может проехать от $i$-го квартала до $j$-го.Далее идут $m$ строк, по четыре числа в каждой: $l_i, r_i$ - номера первого и последнего агентов, затем $s_i, t_i$ - номера стартового и конечного кварталов $(1 <= l_i <= r_i <= n \\; 1 <= s_i, t_i <= 8)$."},{"iden":"выходные данные","content":"Выведите $m$ строк, в $i$-й строке — ответ на $i$-й запрос по модулю $998244353$."},{"iden":"пример","content":"Входные данные3 3\n9241386504218214000\n4692768438333080000\n4620710844295152000\n1 2 3 4\n1 3 1 3\n3 3 1 2\nВыходные данные0\n1\n1\n"},{"iden":"примечание","content":"Переведем данные числа в двоичную систему счисления, дополнив ведущими нулями при необходимости. Получим следующий результат: $9241386504218214000_(10) = 1000000001000000000000000001000000001000000001000000001000000001_2,$$4692768438333080000_(10) = 0100000100100000000100000000100000000100000000100000000110000000_2$,$4620710844295152000_(10) = 0100000000100000000100000000100000000100000000100000000110000000_2$.Теперь составим из полученных чисел матрицы $8 times 8$: $mat(delim: \"(\", 1, 0, 0, 0, 0, 0, 0, 0; 0, 1, 0, 0, 0, 0, 0, 0; 0, 0, 0, 0, 0, 0, 0, 0; 0, 0, 0, 1, 0, 0, 0, 0; 0, 0, 0, 0, 1, 0, 0, 0; 0, 0, 0, 0, 0, 1, 0, 0; 0, 0, 0, 0, 0, 0, 1, 0; 0, 0, 0, 0, 0, 0, 0, 1)$ $mat(delim: \"(\", 0, 1, 0, 0, 0, 0, 0, 1; 0, 0, 1, 0, 0, 0, 0, 0; 0, 0, 0, 1, 0, 0, 0, 0; 0, 0, 0, 0, 1, 0, 0, 0; 0, 0, 0, 0, 0, 1, 0, 0; 0, 0, 0, 0, 0, 0, 1, 0; 0, 0, 0, 0, 0, 0, 0, 1; 1, 0, 0, 0, 0, 0, 0, 0)$ $mat(delim: \"(\", 0, 1, 0, 0, 0, 0, 0, 0; 0, 0, 1, 0, 0, 0, 0, 0; 0, 0, 0, 1, 0, 0, 0, 0; 0, 0, 0, 0, 1, 0, 0, 0; 0, 0, 0, 0, 0, 1, 0, 0; 0, 0, 0, 0, 0, 0, 1, 0; 0, 0, 0, 0, 0, 0, 0, 1; 1, 0, 0, 0, 0, 0, 0, 0)$ В первом запросе необходимо попасть из третьего квартала в четвертый, используя помощь первого и второго агентов. Но первый агент не может переместиться никуда из третьего квартала. Таким образом осуществить побег не удастся.Во втором запросе нужно попасть из первого квартала в третий, используя помощь первого, второго и третьего агентов. Возможный маршрут лишь один: $1 arrow.r 2 arrow.r 3$.В третьем запросе требуется попасть из первого квартала во второй с помощью третьего агента. Это можно сделать ровно одним способом."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $, $ A = (A_1, A_2, \\dots, A_N) $ be a permutation of $ \\{1, 2, \\dots, N\\} $.  \nFor each index $ i \\in \\{1, \\dots, N\\} $, let $ \\mathrm{LIS}_i $ denote the length of the longest increasing subsequence (LIS) of $ A $ that includes $ A_i $.  \nLet $ \\mathrm{LIS}^* = \\max_{i} \\mathrm{LIS}_i $ denote the length of the global LIS of $ A $.\n\n**Constraints**  \n$ 1 \\leq N \\leq 250000 $, and all $ A_i $ are distinct integers in $ [1, N] $.\n\n**Objective**  \nFor each $ i \\in \\{1, \\dots, N\\} $, compute:  \n$$\nf(i) = \\left| \\left\\{ j \\in \\{1, \\dots, N\\} \\setminus \\{i\\} \\mid \\mathrm{LIS}_i^{(j)} < \\mathrm{LIS}_i \\right\\} \\right|\n$$  \nwhere $ \\mathrm{LIS}_i^{(j)} $ is the length of the longest increasing subsequence of the sequence $ A $ with element $ A_j $ removed, that still includes $ A_i $.","simple_statement":"For each position i in a permutation, count how many other positions j (j ≠ i) you can remove so that the longest increasing subsequence passing through i becomes shorter.","has_page_source":false}