Поиски книг о космическом анализе привлекли много внимания, и двое патрульных попытались задержать Рика и Мирлина Теренса. К счастью, на помощь к ним пришла Валлона, и, оглушив нейрохлыстом патрульных, наши герои сбежали обратно в Нижний город. Незамедлительно за ними был выслан целый отряд патрульных, но в Нижнем городе нашелся человек, котрый был готов спрятать беглецов от патрульных. Транторианский агент Матт Хоров укрыл Рика и Валлону в своей пекарне, а Теренс тем временем отправился домой — отсутствие резидента в течение дня могли заметить, а привлекать лишнее внимание Теренс не хотел.

На следующее утро Матт решил отправить Рика и Валлону с Флорины, где им угрожала опасность, на какую-нибудь другую планету. Хоров выдал им поддельные паспорта и билеты на корабль до Вотекса, но оставалась нерешенная проблема — огромное количество патрульных в Верхнем городе. Но Матт Хоров мог использовать других агентов, чтобы доставить Рика и Валлону в космопорт.

Чтобы не привлекать излишнего внимания, Матт решил, что поднимутся они не у самого космопорта, а в каком-либо из $$$8$$$ кварталов Верхнего города, затем проедут по некоторым из этих кварталов, вероятно, не по одному разу, а затем из последнего посещенного квартала отправятся прямо в космопорт. Сопровождать Рика и Валлону будут некоторые из $$$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 \lt l_j \leq r_j \lt r_i$$$.

Для каждого из планов Матт хочет узнать число различных путей, которыми данные агенты могут доставить из стартового квартала в конечный, по модулю $$$998244353$$$. Пути считаются различными, если существует номер $$$l \leq k \leq r$$$, такой что после поездки с $$$k$$$-м агентом по этим путям Рик с Валлоной добрались бы до разных кварталов. Обратите внимание, что для запутывания следов они могут посещать один квартал несколько раз, в том числе подряд.