Happy new year! The year 2020 is also known as Year Gyeongja (경자년, gyeongja-nyeon) in Korea. Where did the name come from? Let's briefly look at the Gapja system, which is traditionally used in Korea to name the years.

There are two sequences of $$$n$$$ strings $$$s_1, s_2, s_3, \ldots, s_{n}$$$ and $$$m$$$ strings $$$t_1, t_2, t_3, \ldots, t_{m}$$$. These strings contain only lowercase letters. There might be duplicates among these strings.

Let's call a concatenation of strings $$$x$$$ and $$$y$$$ as the string that is obtained by writing down strings $$$x$$$ and $$$y$$$ one right after another without changing the order. For example, the concatenation of the strings "code" and "forces" is the string "codeforces".

The year 1 has a name which is the concatenation of the two strings $$$s_1$$$ and $$$t_1$$$. When the year increases by one, we concatenate the next two strings in order from each of the respective sequences. If the string that is currently being used is at the end of its sequence, we go back to the first string in that sequence.

For example, if $$$n = 3, m = 4, s = $$${"a", "b", "c"}, $$$t =$$$ {"d", "e", "f", "g"}, the following table denotes the resulting year names. Note that the names of the years may repeat.

You are given two sequences of strings of size $$$n$$$ and $$$m$$$ and also $$$q$$$ queries. For each query, you will be given the current year. Could you find the name corresponding to the given year, according to the Gapja system?

A sequence $$$a = [a_1, a_2, \ldots, a_l]$$$ of length $$$l$$$ has an ascent if there exists a pair of indices $$$(i, j)$$$ such that $$$1 \le i \lt j \le l$$$ and $$$a_i \lt a_j$$$. For example, the sequence $$$[0, 2, 0, 2, 0]$$$ has an ascent because of the pair $$$(1, 4)$$$, but the sequence $$$[4, 3, 3, 3, 1]$$$ doesn't have an ascent.

Let's call a concatenation of sequences $$$p$$$ and $$$q$$$ the sequence that is obtained by writing down sequences $$$p$$$ and $$$q$$$ one right after another without changing the order. For example, the concatenation of the $$$[0, 2, 0, 2, 0]$$$ and $$$[4, 3, 3, 3, 1]$$$ is the sequence $$$[0, 2, 0, 2, 0, 4, 3, 3, 3, 1]$$$. The concatenation of sequences $$$p$$$ and $$$q$$$ is denoted as $$$p+q$$$.

Gyeonggeun thinks that sequences with ascents bring luck. Therefore, he wants to make many such sequences for the new year. Gyeonggeun has $$$n$$$ sequences $$$s_1, s_2, \ldots, s_n$$$ which may have different lengths.

Gyeonggeun will consider all $$$n^2$$$ pairs of sequences $$$s_x$$$ and $$$s_y$$$ ($$$1 \le x, y \le n$$$), and will check if its concatenation $$$s_x + s_y$$$ has an ascent. Note that he may select the same sequence twice, and the order of selection matters.

Please count the number of pairs ($$$x, y$$$) of sequences $$$s_1, s_2, \ldots, s_n$$$ whose concatenation $$$s_x + s_y$$$ contains an ascent.

Recall that the permutation is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array) and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

A sequence $$$a$$$ is a subsegment of a sequence $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end. We will denote the subsegments as $$$[l, r]$$$, where $$$l, r$$$ are two integers with $$$1 \le l \le r \le n$$$. This indicates the subsegment where $$$l-1$$$ elements from the beginning and $$$n-r$$$ elements from the end are deleted from the sequence.

For a permutation $$$p_1, p_2, \ldots, p_n$$$, we define a framed segment as a subsegment $$$[l,r]$$$ where $$$\max\{p_l, p_{l+1}, \dots, p_r\} - \min\{p_l, p_{l+1}, \dots, p_r\} = r - l$$$. For example, for the permutation $$$(6, 7, 1, 8, 5, 3, 2, 4)$$$ some of its framed segments are: $$$[1, 2], [5, 8], [6, 7], [3, 3], [8, 8]$$$. In particular, a subsegment $$$[i,i]$$$ is always a framed segments for any $$$i$$$ between $$$1$$$ and $$$n$$$, inclusive.

We define the happiness of a permutation $$$p$$$ as the number of pairs $$$(l, r)$$$ such that $$$1 \le l \le r \le n$$$, and $$$[l, r]$$$ is a framed segment. For example, the permutation $$$[3, 1, 2]$$$ has happiness $$$5$$$: all segments except $$$[1, 2]$$$ are framed segments.

Given integers $$$n$$$ and $$$m$$$, Jongwon wants to compute the sum of happiness for all permutations of length $$$n$$$, modulo the prime number $$$m$$$. Note that there exist $$$n!$$$ (factorial of $$$n$$$) different permutations of length $$$n$$$.

Filled with optimism, Hyunuk will host a conference about how great this new year will be!

The conference will have $$$n$$$ lectures. Hyunuk has two candidate venues $$$a$$$ and $$$b$$$. For each of the $$$n$$$ lectures, the speaker specified two time intervals $$$[sa_i, ea_i]$$$ ($$$sa_i \le ea_i$$$) and $$$[sb_i, eb_i]$$$ ($$$sb_i \le eb_i$$$). If the conference is situated in venue $$$a$$$, the lecture will be held from $$$sa_i$$$ to $$$ea_i$$$, and if the conference is situated in venue $$$b$$$, the lecture will be held from $$$sb_i$$$ to $$$eb_i$$$. Hyunuk will choose one of these venues and all lectures will be held at that venue.

Two lectures are said to overlap if they share any point in time in common. Formally, a lecture held in interval $$$[x, y]$$$ overlaps with a lecture held in interval $$$[u, v]$$$ if and only if $$$\max(x, u) \le \min(y, v)$$$.

We say that a participant can attend a subset $$$s$$$ of the lectures if the lectures in $$$s$$$ do not pairwise overlap (i.e. no two lectures overlap). Note that the possibility of attending may depend on whether Hyunuk selected venue $$$a$$$ or venue $$$b$$$ to hold the conference.

A subset of lectures $$$s$$$ is said to be venue-sensitive if, for one of the venues, the participant can attend $$$s$$$, but for the other venue, the participant cannot attend $$$s$$$.

A venue-sensitive set is problematic for a participant who is interested in attending the lectures in $$$s$$$ because the participant cannot be sure whether the lecture times will overlap. Hyunuk will be happy if and only if there are no venue-sensitive sets. Determine whether Hyunuk will be happy.

Kiwon's favorite video game is now holding a new year event to motivate the users! The game is about building and defending a castle, which led Kiwon to think about the following puzzle.

In a 2-dimension plane, you have a set $$$s = \{(x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)\}$$$ consisting of $$$n$$$ distinct points. In the set $$$s$$$, no three distinct points lie on a single line. For a point $$$p \in s$$$, we can protect this point by building a castle. A castle is a simple quadrilateral (polygon with $$$4$$$ vertices) that strictly encloses the point $$$p$$$ (i.e. the point $$$p$$$ is strictly inside a quadrilateral).

Kiwon is interested in the number of $$$4$$$-point subsets of $$$s$$$ that can be used to build a castle protecting $$$p$$$. Note that, if a single subset can be connected in more than one way to enclose a point, it is counted only once.

Let $$$f(p)$$$ be the number of $$$4$$$-point subsets that can enclose the point $$$p$$$. Please compute the sum of $$$f(p)$$$ for all points $$$p \in s$$$.

Donghyun's new social network service (SNS) contains $$$n$$$ users numbered $$$1, 2, \ldots, n$$$. Internally, their network is a tree graph, so there are $$$n-1$$$ direct connections between each user. Each user can reach every other users by using some sequence of direct connections. From now on, we will denote this primary network as $$$T_1$$$.

To prevent a possible server breakdown, Donghyun created a backup network $$$T_2$$$, which also connects the same $$$n$$$ users via a tree graph. If a system breaks down, exactly one edge $$$e \in T_1$$$ becomes unusable. In this case, Donghyun will protect the edge $$$e$$$ by picking another edge $$$f \in T_2$$$, and add it to the existing network. This new edge should make the network be connected again.

Donghyun wants to assign a replacement edge $$$f \in T_2$$$ for as many edges $$$e \in T_1$$$ as possible. However, since the backup network $$$T_2$$$ is fragile, $$$f \in T_2$$$ can be assigned as the replacement edge for at most one edge in $$$T_1$$$. With this restriction, Donghyun wants to protect as many edges in $$$T_1$$$ as possible.

Formally, let $$$E(T)$$$ be an edge set of the tree $$$T$$$. We consider a bipartite graph with two parts $$$E(T_1)$$$ and $$$E(T_2)$$$. For $$$e \in E(T_1), f \in E(T_2)$$$, there is an edge connecting $$$\{e, f\}$$$ if and only if graph $$$T_1 - \{e\} + \{f\}$$$ is a tree. You should find a maximum matching in this bipartite graph.

It is only a few days until Seollal (Korean Lunar New Year), and Jaehyun has invited his family to his garden. There are kids among the guests. To make the gathering more fun for the kids, Jaehyun is going to run a game of hide-and-seek.

The garden can be represented by a $$$n \times m$$$ grid of unit cells. Some (possibly zero) cells are blocked by rocks, and the remaining cells are free. Two cells are neighbors if they share an edge. Each cell has up to 4 neighbors: two in the horizontal direction and two in the vertical direction.

Since the garden is represented as a grid, we can classify the cells in the garden as either "black" or "white". The top-left cell is black, and two cells which are neighbors must be different colors. Cell indices are 1-based, so the top-left corner of the garden is cell $$$(1, 1)$$$.

Jaehyun wants to turn his garden into a maze by placing some walls between two cells. Walls can only be placed between neighboring cells. If the wall is placed between two neighboring cells $$$a$$$ and $$$b$$$, then the two cells $$$a$$$ and $$$b$$$ are not neighboring from that point. One can walk directly between two neighboring cells if and only if there is no wall directly between them.

A maze must have the following property. For each pair of free cells in the maze, there must be exactly one simple path between them. A simple path between cells $$$a$$$ and $$$b$$$ is a sequence of free cells in which the first cell is $$$a$$$, the last cell is $$$b$$$, all cells are distinct, and any two consecutive cells are neighbors which are not directly blocked by a wall.

At first, kids will gather in cell $$$(1, 1)$$$, and start the hide-and-seek game. A kid can hide in a cell if and only if that cell is free, it is not $$$(1, 1)$$$, and has exactly one free neighbor. Jaehyun planted roses in the black cells, so it's dangerous if the kids hide there. So Jaehyun wants to create a maze where the kids can only hide in white cells.

You are given the map of the garden as input. Your task is to help Jaehyun create a maze.