小R与小W在玩游戏。
他们有一个边数为n的凸多边形，其顶点沿逆时针方向标号依次为。最开始凸多边形中有n条线段，即多边形的n条边。这里我们用一个有序数对(a,b)（其中a<b）来表示一条端点分别为顶点a,b的线段。
在游戏开始之前，小W会进行一些操作。每次操作时，他会选中多边形的两个互异顶点，给它们之间连一条线段，并且所连的线段不会与已存的线段重合、相交（只拥有一个公共端点不算作相交）。他会不断重复这个过程，直到无法继续连线，这样得到了状态。包含的线段为凸多边形的边与小W连上的线段，容易发现这些线段将多边形划分为一个个三角形区域。对于其中任意一个三角形，其三个顶点为i,j,k(i<j<k)，我们可以给这个三角形一个标号j，这样一来每个三角形都被标上了中的一个，且没有标号相同的两个三角形。
小W定义了一种「旋转」操作：对于当前状态，选定4个顶点a,b,c,d，使其满足1≤a<b<c<d≤n且它们两两之间共有5条线段——(a,b),(b,c),(c,d),(a,d),(a,c)，然后删去线段(a,c)，并连上线段(b,d)。那么用有序数对(a,c)即可唯一表示该次「旋转」。我们称这次旋转为(a,c)「旋转」。显然每次进行完“旋转”操作后多边形中依然不存在相交的线段。
当小W将一个状态作为游戏初始状态展示给小R后，游戏开始。游戏过程中，小R每次可以对当前的状态进行「旋转」。在进行有限次「旋转」之后，小R一定会得到一个状态，此时无法继续进行「旋转」操作，游戏结束。那么将每一次「旋转」所对应的有序数对按操作顺序写下，得到的序列即为该轮游戏的操作方案。
为了加大难度，小W以为基础，产生了m个新状态。其中第i个状态为对进行一次「旋转」操作后得到的状态。你需要帮助小R求出分别以作为游戏初始状态时，小R完成游戏所用的最少「旋转」次数，并根据小W的心情，有时还需求出旋转次数最少的不同操作方案数。由于方案数可能很大，输出时请对取模。

第一行一个整数W，表示小W的心情。若W为0则只需求出最少的「旋转」次数，若W为1则还需求出「旋转」次数最少时的不同操作方案数。
第二行一个正整数n，表示凸多边形的边数。
接下来n-3行，每行两个正整数x,y，表示小W在中连的一条线段，端点分别为x,y。保证该线段不与已存的线段重合或相交。
接下来一行一个整数m，表示小W以为基础产生的新状态个数。
接下来m行，每行两个整数。假设其中第i行为a,b，表示对进行(a,b)「旋转」后得到。

输出共m+1行。
若W为0则每一行输出一个整数，第行输出的整数表示作为初始局面的最少「旋转」次数。
若W为1则每一行输出两个整数，第行输出的两个整数依次表示作为初始局面的最少「旋转」次数、「旋转」次数最少的不同操作方案数对取模的结果。

1
6
1 3
1 5
3 5
1
1 3

3 2
3 1

以为初始状态，最少「旋转」次数为3，有2种方案，如下：
以为初始状态，最少「旋转」次数为3，有1种方案，如下：

1
12
1 10
1 6
1 3
3 6
3 5
6 10
6 8
8 10
10 12
4
1 10
1 3
6 8
1 6

8 210
7 210
8 70
8 105
8 140

对于所有输入数据，保证：。