Problems - Codeforces

NOIP 2022

小 C 决定在他的花园里种出 CCF 字样的图案，因此他想知道 C 和 F 两个字母各自有多少种种花的方案；不幸的是，花园中有一些土坑，这些位置无法种花，因此他希望你能帮助他解决这个问题。

花园可以看作有 n × m 个位置的网格图，从上到下分别为第 1 到第 n 行，从左到右分别为第 1 列到第 m 列，其中每个位置有可能是土坑，也有可能不是，可以用 a_i, j = 1 表示第 i 行第 j 列这个位置有土坑，否则用 a_i, j = 0 表示这个位置没土坑。

一种种花方案被称为 C - 形的，如果存在 $\text{[math]}$ ，以及 $\text{[math]}$ ，满足 x₁ + 1 < x₂，并且 y₀ < y₁, y₂ ≤ m，使得第 x₁ 行的第 y₀ 到第 y₁ 列、第 x₂ 行的第 y₀ 到第 y₂ 列以及第 y₀ 列的第 x₁ 到第 x₂ 行都不为土坑，且只在上述这些位置上种花。

一种种花方案被称为 F - 形的，如果存在 $\text{[math]}$ ，以及 $\text{[math]}$ ，满足 x₁ + 1 < x₂ < x₃，并且 y₀ < y₁, y₂ ≤ m，使得第 x₁ 行的第 y₀ 到第 y₁ 列、第 x₂ 行的第 y₀ 到第 y₂ 列以及第 y₀ 列的第 x₁ 到第 x₃ 行都不为土坑，且只在上述这些位置上种花。

样例一解释中给出了 C - 形和 F - 形种花方案的图案示例。

现在小 C 想知道，给定 n, m 以及表示每个位置是否为土坑的值 {a_i, j}，C - 形和 F - 形种花方案分别有多少种可能？由于答案可能非常之大，你只需要输出其对 998244353 取模的结果即可，具体输出结果请看输出格式部分。

Input

从文件 'plant.in' 读入。

第一行包含两个整数 T, id，分别表示数据组数和测试点编号。如果数据为样例则保证 id = 0。在这里测试点编号没用！

接下来一共 T 组数据，在每组数据中：

第一行包含四个整数 n, m, c, f，其中 n, m 分别表示花园的行数、列数，对于 c, f 的含义见输出格式部分。

接下来 n 行，每行包含一个长度为 m 且仅包含 0 和 1 的字符串，其中第 i 个串的第 j 个字符表示 a_i, j，即花园里的第 i 行第 j 列是不是一个土坑。

Output

输出至文件 'plant.out'。

设花园中 C - 形和 F - 形的种花方案分别有 V_C 和 V_F 种，则你需要对每一组数据输出一行用一个空格隔开的两个非负整数，分别表示 $\text{[math]}$ ， $\text{[math]}$ ，其中 $\text{[math]}$ 表示 a 对 P 取模后的结果。

Examples

Input

Output

4 2

Input

Output

36 18

Input

1 0
16 12 1 1
000000000001
011111111111
000000000011
011111111111
010011111111
010111100011
010011101111
011111100011
111111111111
000011111111
011111111111
000000111111
011111000111
011111011111
011111000111
011111011111

Output

114 514

Note

$\text{[math]}$

小 E 喜欢上了一款叫做《喵了个喵》的游戏。这个游戏有一个牌堆和 n 个可以从栈底删除元素的栈，任务是要通过游戏规则将所有的卡牌消去。开始时牌堆中有 m 张卡牌，从上到下的图案分别是 a₁, a₂, ..., a_m。所有的卡牌一共有 k 种图案，从 1 到 k 编号。牌堆中每一种图案的卡牌都有偶数张。开始时所有的栈都是空的。这个游戏有两种操作：

选择一个栈，将牌堆顶上的卡牌放入栈的顶部。如果这么操作后，这个栈最上方的两张牌有相同的图案，则会自动将这两张牌消去。
选择两个不同的栈，如果这两个栈栈底的卡牌有相同的图案，则可以将这两张牌消去，原来在栈底上方的卡牌会成为新的栈底。如果不同，则什么也不会做。

这个游戏一共有 T 关，小 E 一直无法通关。请你帮小 E 设计一下游戏方案，即对于游戏的每一关，给出相应的操作序列使得小 E 可以把所有的卡牌消去。

Input

从文件 'meow.in' 读入。

第一行包含一个正整数 T，表示数据组数。

接下来一共 T 组数据，在每组数据中：

第一行包含三个正整数 n, m, k，分别表示栈的个数、卡牌的个数、卡牌上图案的种类。

第二行包含 m 个正整数，分别表示 a₁, a₂, ..., a_m，分别从上到下表示牌堆中卡牌的图案。

输入数据保证有解。

Output

输出至文件 'meow.out'。

对于每一组数据，输出若干行。

其中第一行包含一个正整数 op，表示操作的次数。你需要保证 m ≤ op ≤ 2 × m。

接下来 op 行，每行包含两个或三个正整数，整数之间用一个空格隔开。

若为两个整数 '1 s'，则进行一次第一个操作并选择栈 s。

若为三个整数 '2 s1 s2'，则进行一次第二个操作并选择栈 s₁ 和 s₂。

你需要保证 1 ≤ s, s₁, s₂ ≤ n，且 s₁ ≠ s₂。

Example

Input

1
2 4 2
1 2 1 2

Output

Note

设 S 为所有 T 组数据中 m 的总和。

S ≤ 2 × 10⁶, 1 ≤ n ≤ 300, 1 ≤ a_i ≤ k

对于每一组数据，若在按顺序进行所有操作后，牌堆为空且所有的栈均为空，则认为你的答案正确。

你的输出不需要与样例输出一致，输出任意一个合法解即可得分。

A 国与 B 国正在激烈交战中，A 国打算在自己的国土上建造一些军营。

A 国的国土由 n 座城市组成，m 条双向道路连接这些城市，使得任意两座城市均可通过道路直接或间接到达。A 国打算选择一座或多座城市（至少一座），并在这些城市上各建造一座军营。

众所周知，军营之间的联络是十分重要的。然而此时 A 国接到情报，B 国将会于不久后袭击 A 国的一条道路，但具体的袭击目标却无从得知。如果 B 国袭击成功，这条道路将被切断，可能会造成 A 国某两个军营无法互相到达，这是 A 国极力避免的。因此 A 国决定派兵看守若干条道路（可以是一条或多条，也可以一条也不看守，A 国有信心保证被派兵看守的道路能够抵御 B 国的袭击而不被切断。

A 国希望制定一个建造军营和看守道路的方案，使得 B 国袭击的无论是 A 国的哪条道路，都不会造成某两座军营无法互相到达。现在，请你帮 A 国计算一下可能的建造军营和看守道路的方案数共有多少。由于方案数可能会很多，你只需要输出其对 1, 000, 000, 007 取模的值即可。两个方案被认为是不同的，当且仅当存在至少一座城市在一个方案中建造了军营而在另一个方案中没有，或者存在至少一条道路在一个方案中被派兵看守而在另一个方案中没有。

Input

从文件 'barrack.in' 读入。

第一行包含两个正整数 n, m，分别表示城市的个数和双向道路的数量。

接下来 m 行，每行包含两个正整数 u_i, v_i，描述一条连接 u_i 和 v_i 的双向道路。保证没有重边和自环。

Output

输出至文件 'barrack.out'

输出一行包含一个整数，表示建造军营和看守道路的方案数对 1, 000, 000, 007 取模的结果。

Examples

Input

2 1
1 2

Output

Input

Output

Note

1 ≤ n ≤ 5 × 10⁵, n - 1 ≤ m ≤ 10⁶, 1 ≤ u_i, v_i ≤ n, u_i ≠ v_i

小 N 和小 O 会在 2022 年 11 月参加一场盛大的程序设计大赛 NOIP！小 P 会作为裁判主持竞赛。小 N 和小 O 各自率领了一支 n 个人的队伍，选手在每支队伍内都是从 1 到 n 编号。每一个选手都有相应的程序设计水平。具体的，小 N 率领的队伍中，编号为 i（1 ≤ i ≤ n）的选手的程序设计水平为 a_i；小 O 率领的队伍中，编号为 i（1 ≤ i ≤ n）的选手的程序设计水平为 b_i。特别地，a_i 和 b_i 还分别构成了从 1 到 n 的排列。

每场比赛前，考虑到路途距离，选手连续参加比赛等因素，小 P 会选择两个参数 l, r（1 ≤ l ≤ r ≤ n），表示这一场比赛会邀请两队中编号属于 [l, r] 的所有选手来到现场准备比赛。在比赛现场，小 N 和小 O 会以掷骰子的方式挑选出参数 p, q（l ≤ p ≤ q ≤ r），只有编号属于 [p, q] 的选手才能参赛。为了给观众以最精彩的比赛，两队都会派出编号在 [p, q] 内的、程序设计水平值最大的选手参加比赛。假定小 N 派出的选手水平为 m_a，小 O 派出的选手水平为 m_b，则比赛的精彩程度为 m_a × m_b。

NOIP 总共有 Q 场比赛，每场比赛的参数 l, r 都已经确定，但是 p, q 还没有抽取。小 P 想知道，对于每一场比赛，在其所有可能的 p, q（l ≤ p ≤ q ≤ r）参数下的比赛的精彩程度之和。由于答案可能非常之大，你只需要对每一场答案输出结果对 2⁶⁴ 取模的结果即可。

Input

从文件 'match.in' 读入。

第一行包含两个正整数 T, n，分别表示测试点编号和参赛人数。如果数据为样例则保证 T = 0。

第二行包含 n 个正整数，第 i 个正整数为 a_i，表示小 N 队伍中编号为 i 的选手的程序设计水平。

第三行包含 n 个正整数，第 i 个正整数为 b_i，表示小 O 队伍中编号为 i 的选手的程序设计水平。

第四行包含一个正整数 Q，表示比赛场数。

接下来的 Q 行，第 i 行包含两个正整数 l_i, r_i，表示第 i 长比赛的参数 l, r。

Output

输出至文件 'match.out'。

输出 Q 行，第 i 行包含一个非负整数，表示第 i 场比赛中所有可能的比赛的精彩程度之和对 2⁶⁴ 取模的结果。

Example

Input

Output

Note

1 ≤ n, Q ≤ 2.5 × 10⁵, 1 ≤ l_i ≤ r_i ≤ n, 1 ≤ a_i, b_i ≤ n

a_i 和 b_i 分别构成了从 1 到 n 的排列。