“华为杯” 2024 年广东工业大学 ACM 新生程序设计竞赛（决赛）
A. 演奏春日影
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output
"演唱会时别突然弹吉他，灯的 MC 结束后才可以弹。"
— 椎名立希

作为 MyGO 乐队的主唱吉他，乐奈非常认真负责地履行着立希跟她说的这句话。因此她在看到乐队的演出节目单的时候，都会在每一个表示的灯的 MC 的 "Tomori" 后面自动脑补上一首 "Haruhikage"（均不包括引号，区分大小写）。

演奏春日影

现在给出 MyGO 乐队的演出节目单，请你输出乐奈脑补完之后的节目单。

Input

第一行一个整数 $$$n$$$ ($$$1\le n\le 100$$$)，表示原本节目的数量。 接下来 $$$n$$$ 行，每行一个长度不超过 $$$20$$$ 的字符串，且仅包含大小写字母，表示一个节目。

Output

按顺序输出补完之后的节目单，每行输出一个字符串，表示一个节目。

Examples
Input
2
Hekitenbansou
Tomori
Output
Hekitenbansou
Tomori
Haruhikage
Input
5
Tomorin
Neko
Rikki
AnonTokyo
Soyorin
Output
Tomorin
Neko
Rikki
AnonTokyo
Soyorin
Input
4
Tomori
TOMORI
Tomori
Tomo
Output
Tomori
Haruhikage
TOMORI
Tomori
Haruhikage
Tomo
Input
1
NadeHaruhikageyatano
Output
NadeHaruhikageyatano
Note

第一组样例中，在灯的 MC 即"Tomori"之后，乐奈自动演奏起了"Haruhikage"。

B. 超平坦棋盘
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

雪碧喜欢玩 Minecraft 和国际象棋，这天他建立了一个超平坦的棋盘世界，世界是一个无尽大小的国际象棋棋盘，其中在最初棋盘上的所有格子都有一只马。棋盘本身是一个无穷大的二维矩阵，每个格子都有一个相应的整数坐标，可以为负。

这天，游戏触发了一个奖励事件。在事件中，位于棋盘坐标 $$$(n, m)$$$ 的马被移除了，留下了一个空格。同时，位于棋盘坐标 $$$(0, 0)$$$ 的马被升级成为了超级马，奖励事件的目标是将超级马移动到 $$$(n, m)$$$ 的位置。

雪碧可以移动任意种类的马，但要求过程中任意类型的马都不能同时在同一个格子中，并且移动任何马的次数之和最小。

可怜的雪碧不知道如何移动这些马来达成目标，所以他决定请教你，最少需要移动多少次才能完成这个目标。

马的移动规则是：如果马位于 $$$(x, y)$$$ 的位置，那么它可以移动到 $$$(x \pm 1, y \pm 2)$$$ 或 $$$(x \pm 2, y \pm 1)$$$ 的位置，当且仅当目标位置上没有其他马。

Input

第一行包含一个整数 $$$T$$$ ($$$1 \le T \le 100$$$)，表示测试用例数。

接下来 $$$T$$$ 行，每行包含两个整数 $$$n, m$$$ ($$$1 \le n, m \le 10^5$$$, $$$n \cdot m \le 10^5$$$)，表示目标位置的坐标。

保证所有测试用例的 $$$n \cdot m$$$ 之和不大于 $$$10^5$$$。

Output

对于每个测试用例，输出一行一个整数，表示最少需要移动的次数。

Example
Input
5
3 3
4 4
5 5
6 6
7 7
Output
5
13
15
13
21
Note

对于第一组样例：

初始时，只有 $$$(3, 3)$$$ 为空第一步：$$$(1, 2) \to (3, 3)$$$第二步：$$$(0, 0) \to (1, 2)$$$
第三步：$$$(2, 1) \to (0, 0)$$$第四步：$$$(3, 3) \to (2, 1)$$$第五步：$$$(1, 2) \to (3, 3)$$$

可以证明，不存在更优方案。

C. 交通要塞
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

G 大有一条路会在每次上下课时变得十分拥堵，有时甚至堵得一动不动。然而，堵住的路就是饭堂排着的队，饿坏了的你深知，自己必须穿过这堵死的交通要塞。

虽然每条车道几乎全部堵死，但却各自刚好留有一段空位。

具体来说，我们可以将要塞抽象为一个二维整点平面。有 $$$0,1,2,\dots,n,n+1$$$ 共 $$$n+2$$$ 条车道，初始时你在 $$$0$$$ 号车道，位于 $$$(0, 0)$$$，你的目标是抵达 $$$n+1$$$ 号车道，即抵达 $$$(n+1, 0)$$$。$$$0$$$ 号车道和 $$$n+1$$$ 号车道其实是人行道，所以没有车，故全车道畅通无阻。而对于第 $$$1,2,\dots,n$$$ 号车道中的第 $$$i$$$ 条车道，有一小段没有车的区域为 $$$(i, l_i)$$$ 到 $$$(i, r_i)$$$。

然而自行车们不会等你慢慢通过。每一秒，自行车海会整体向负方向移动一个单位。即所有的 $$$l_i$$$ 和 $$$r_i$$$ 将减少 $$$1$$$。

人行道的区域并不大，因此在每一秒，你唯一能进行的决策，就是是否前进一个单位 $$$(x, 0) \to (x+1,0)$$$，或者停留一次 $$$(x, 0) \to (x, 0)$$$。

因为你身手敏捷，所以我们认为你和自行车的移动都是同时瞬间完成的。因此，每一秒进行移动后，只要你位于没有车的区域，就是合法的移动。

为了尽快去到饭堂，你希望知道，最少需要花费多少单位的时间，才能抵达终点。

Input

第一行一个整数 $$$n$$$ ($$$1\le n\le 10^5$$$)，代表车道数。

接下来 $$$n$$$ 行，第 $$$i$$$ 行两个整数 $$$l_i, r_i$$$ ($$$0\le l\le r\le 10^{12}$$$)，表示第 $$$i$$$ 条车道没有车的区域。

Output

如果可以到达终点，请输出一个整数，表示最少需要花费多少单位的时间；如果无法到达终点，请输出 $$$-1$$$。

Examples
Input
4
1 2
2 3
4 5
5 6
Output
6
Input
4
1 2
3 5
1 6
1 2
Output
-1
Input
1
0 0
Output
-1
Input
1
1000000000000 1000000000000
Output
1000000000001
Note

对于第一组样例，一种合法的方案是：前进、前进、停留、前进、前进、前进。

D. 魔法少女素世世
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output
"和我签订契约，成为魔法少女吧！"
— Incubator
"只要是我能做的，我什么都愿意做！"
— Soyorin

为了复活 CRYCHIC，素世与丘比签订契约成为了魔法少女，但代价是素世需要讨伐魔女以补充足够的魔力。

现在素世正准备去讨伐迷途的魔女，迷途的魔女藏身在一个有 $$$n$$$ 个房间的迷宫内，并且拥有 $$$n-1$$$ 个分身。其中，魔女的本体位于编号为 $$$n$$$ 的房间内，而魔女的分身分别位于编号 $$$1$$$ 到 $$$n-1$$$ 的房间。

这些房间之间由单向的通道连接，每个房间都有单向通往其它的房间的通道。其中，如果一个房间不能通过通道进入，则代表它可以直接通过迷宫入口进入，即你可以直接从这里开始讨伐。

由于迷途的魔女本身的特性，这个迷宫保证了，从每个房间出发都可以到达第 $$$n$$$ 号房间，并且通道不会在房间之间成环。

每个魔女都有相应的魔力值，第 $$$i$$$ 个房间的魔女的魔力值为 $$$a_i$$$。当素世在房间内遇到魔女时，素世会与魔女展开战斗。

假设当前素世的魔力值为 $$$x$$$：

  • 如果 $$$x\ge a_i$$$，素世可以轻松消灭魔女，并且素世的魔力值 $$$x$$$ 会增加 $$$a_i$$$

  • 否则，素世只能勉强消灭魔女，并且素世的魔力值 $$$x$$$ 会减少 $$$a_i-x$$$。

在任何时刻，如果素世的魔力值 $$$x\le 0$$$，那么素世就失败了。

因此素世想知道，要成功打败魔女本体，即消灭位于 $$$n$$$ 号房间内的魔女，至少需要有多少魔力值才能进入迷宫内？

Input

第一行两个整数 $$$n,m$$$ ($$$1\le n\le 10^5, 0\le m\le 2\cdot 10^5$$$)，分别表示迷宫的房间数量，和房间之间单向通道的数量。

第二行 $$$n$$$ 个整数，第 $$$i$$$ 个整数表示第 $$$i$$$ 个房间的魔女的魔力值 $$$a_i$$$ ($$$1\le a_i\le 10^9$$$)。

接下来 $$$m$$$ 行，每行两个整数 $$$u,v$$$ ($$$1\le u,v\le n$$$)，表示一条从 $$$u$$$ 号房间通往 $$$v$$$ 号房间的单向通道。

数据保证给定图不存在重边和自环，且是一个有向无环图。

Output

一行一个整数，表示最少所需的进入迷宫的魔力值。

Examples
Input
1 0
1
Output
1
Input
4 3
1 2 5 5
1 3
2 3
3 4
Output
2
Input
8 10
3 2 1 2 3 4 3 2
1 2
1 4
2 3
2 4
3 4
4 6
5 8
5 6
6 8
7 8
Output
3
Note

对于样例 1：

  • 唯一的房间（房间 $$$1$$$）里有魔女本体，魔力值为 $$$1$$$。
  • 素世至少需要魔力值 $$$x = 1$$$ 才能进入迷宫并击败魔女。

对于样例 2：

  • 如果从房间 $$$1$$$ 开始，需要至少 $$$x = 3$$$ 的魔力值：击败房间 $$$1$$$ 的魔女后，$$$x=3+1=4$$$。
  • 如果从房间 $$$2$$$ 开始，需要至少 $$$x = 2$$$ 的魔力值：击败房间 $$$2$$$ 的魔女后，$$$x=2+2=4$$$。
  • 然后通过房间 $$$3$$$，击败房间 $$$3$$$ 的魔女后，$$$x=4-(5-4)=3$$$。
  • 然后通过房间 $$$4$$$，击败房间 $$$4$$$ 的魔女后，$$$x=3-(5-3)=1$$$。
  • 因此素世至少需要魔力值 $$$x = 2$$$ 才能进入迷宫并击败魔女。

E. 黑塔的奇物
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

由于最近黑塔忙着探索模拟宇宙的不可知域，空间站对新增奇物的管理非常混乱。而作为黑塔空间站的临时奇物管理员的开拓者，决定亲自安放这些奇物。

奇物收容仓

这些奇物共有 $$$n$$$ 种，分别从 $$$1$$$ 到 $$$n$$$ 编号，每种奇物都恰好有 $$$n$$$ 个，即一共有 $$$n \times n$$$ 个奇物。开拓者决定把这些奇物安置到一个专门用来收容奇物的 $$$n \times n$$$ 大小的棋盘上。

但是开拓者发现，这些奇物会与棋盘耦合并互相产生一些奇妙的影响，导致在这个棋盘中，每一行和每一列的 $$$n$$$ 个奇物都会在这一行或者这一列产生一个紊乱值，而紊乱值的大小为这 $$$n$$$ 个奇物编号的异或和$$$\dagger$$$。

如果有某一行或者某一列的紊乱值超过阈值 $$$m$$$，可能会导致这些奇物被棋盘破坏。因此，开拓者想知道如果以最优方案摆放这些奇物，阈值 $$$m$$$ 最低可以设置到多少。

开拓者想让你给出最优方案摆放方案下阈值 $$$m$$$ 的最小值，以及把这 $$$n \times n$$$ 个奇物摆放在棋盘上的具体方案。

$$$\dagger$$$ 异或和，即所有数的按位异或和。如 $$$1, 3, 4$$$ 的按位异或和是 $$$(001)_2 \oplus (011)_2 \oplus (100)_2 = (110)_2 = 6$$$

Input

一行一个正整数 $$$n$$$ ($$$1\le n \lt 500$$$, 且保证 $$$n$$$ 是奇数) 表示奇物的种类以及每种奇物的数量。

Output

第一行一个正整数 $$$m$$$ 表示最优方案下的紊乱值。

接下来输出一个 $$$n$$$ 行 $$$n$$$ 列的矩阵，表示一种最优方案。如果存在多个可行方案，输出任意一种。

Examples
Input
1
Output
1
1
Input
3
Output
0
1 2 3
2 3 1
3 1 2
Note

注意到 $$$n$$$ 是奇数。

F. 字符串缩写太多了！
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

八奈见杏菜是字符串低手。一日，佳树给来到温水家的杏菜出了一道题。

我们定义：

  • 一个缩写是取有序的若干字符串的首字母拼接形成的。如：abc bcd def 的缩写为 abd。
  • 一个缩写的方案数是通过选取若干个字符串按一定顺序取得该缩写的方案数。如：如果给定三个字符串 aaa aab baa，那么缩写 aab 的方案数是 $$$2$$$，分别为 aaa aab baa 和 aab aaa baa。

现在给定 $$$n$$$ 个各不相同的英文小写字母字符串，求出这些字符串能构成的所有缩写的方案数之和，答案对 $$$10^9+7$$$ 取模。

然而杏菜对这题无能为力，但她知道你是字符串高手，于是请你帮她写了这题。

$$$\texttt{T}_{\texttt{\^{}}}\texttt{T}$$$
Input

第一行一个整数 $$$n$$$，表示字符串的数量 $$$(1 \leq n \leq 10^5)$$$。

接下来的 $$$n$$$ 行，每行是一个只有小写英文字母的字符串。保证所有字符串各不相同。

保证所有读入的字符串长度和不大于 $$$10^6$$$

Output

对于每组测试用例，输出一个整数，表示所有缩写的方案数之和，答案对 $$$10^9+7$$$ 取模。

Examples
Input
3
aaa
aab
bba
Output
15
Input
5
ya
na
mi
an
naa
Output
325
Note

对于样例：

  • 缩写 a 的方案有 $$$2$$$ 种：aaa、aab。
  • 缩写 b 的方案有 $$$1$$$ 种：bba。
  • 缩写 aa 的方案有 $$$2$$$ 种：aaa aab、aab aaa。
  • 缩写 ab 的方案有 $$$2$$$ 种：aaa bba、aab bba。
  • 缩写 ba 的方案有 $$$2$$$ 种：bba aaa、bba aab。
  • 缩写 aab 的方案有 $$$2$$$ 种：aaa aab bba、aab aaa bba。
  • 缩写 aba 的方案有 $$$2$$$ 种：aaa bba aab、aab bba aaa。
  • 缩写 baa 的方案有 $$$2$$$ 种：bba aaa aab、bba aab aaa。

共有 $$$2+1+2+2+2+2+2+2=15$$$ 种方案

G. 可乐喝雪碧
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

本题与"雪碧喝可乐"是不同的，你可能需要分别阅读两个版本。两题区别在于 $$$q$$$ 和 $$$x$$$ 的限制条件不同，在这个版本中，$$$q = 1$$$，且 $$$x = 0$$$。

从前有一只可乐，他每天都一定会去商店买一瓶雪碧。每天商店出售的雪碧的口味可能以下是三种之一：

  1. 经典口味，可乐的最爱，可乐喝完后有 $$$+1$$$ 的快乐值。

  2. 无糖口味，感觉很一般，可乐喝完后有 $$$0$$$ 的快乐值。

  3. 柠檬口味，可乐的噩梦，可乐喝完后有 $$$-1$$$ 的快乐值。

每天可乐买完雪碧后不一定当天喝完，他可以囤积若干瓶雪碧，然后在将来的某一天，把囤积的所有雪碧一口气喝完。可乐一次喝完若干雪碧后获得的快乐值为一次喝的所有雪碧的快乐值之积。可乐能得到的快乐值的总和是若干次喝雪碧的快乐值之和。

现在可乐通过魔法获知了未来 $$$n$$$ 天商店的雪碧出售情况数组 $$$a$$$，其中 $$$a_i$$$ 代表未来第 $$$i$$$ 天商店出售的雪碧的快乐值。他突发奇想，想知道他能否通过囤积和一口气喝完的手段，在把未来 $$$n$$$ 天的所有雪碧都喝完后，获得恰好 $$$x$$$ 的快乐值的总和。

乐于思考的可乐连续想了 $$$q$$$ 个这样的问题，并期待你给他回答。

形式化地，给定长度为 $$$n$$$ 的由 $$$-1, 0, 1$$$ 组成的数组 $$$a$$$，询问是否存在一种方案通过在所有相邻的两数之间填入共 $$$n-1$$$ 个加号和乘号所形成的数学表达式的求值为 $$$x$$$。

Input

第一行一个整数 $$$T$$$ ($$$1\le T\le 10^4$$$)，代表测试用例数。

对于每组测试用例：

  • 第一行两个整数 $$$n,q$$$ ($$$1\le n\le 10^6$$$, $$$q = 1$$$) 分别表示未来天数和询问次数。
  • 第二行 $$$n$$$ 个整数，其中第 $$$i$$$ 个整数 $$$a_i$$$ ($$$a_i\in \{-1,0,1\}$$$) 表示未来第 $$$i$$$ 天商店出售的雪碧的快乐值。
  • 接下来 $$$q$$$ 行，每行一个整数 $$$x$$$ ($$$x = 0$$$)，表示可乐的一个询问。

保证所有测试用例的 $$$n$$$ 之和与 $$$q$$$ 之和均不大于 $$$10^6$$$。

Output

对于每一个询问，如果满足条件则输出一行 Yes，否则输出一行 No。

你可以以任意大小写输出 Yes 和 No（例如，字符串 yEs、yes、Yes 和 YES 将被识别为肯定的回答）。

Example
Input
4
3 1
1 1 0
0
3 1
1 -1 -1
0
4 1
-1 -1 -1 -1
0
5 1
-1 -1 1 -1 -1
0
Output
YES
NO
NO
YES
Note

对于第一个测试用例，显然可以通过方案 $$$1 \times 1 \times 0 = 0$$$ 得到快乐值 $$$0$$$。

H. 雪碧喝可乐
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

本题与"可乐喝雪碧"是不同的，你可能需要分别阅读两个版本。两题区别在于 $$$q$$$ 和 $$$x$$$ 的限制条件不同，在这个版本中，$$$1 \le q \le 10^6$$$，且 $$$1\le x \le 10^6$$$。

从前有一只雪碧，他每天都一定会去商店买一瓶可乐。每天商店出售的可乐的口味可能以下是三种之一：

  1. 经典口味，雪碧的最爱，雪碧喝完后有 $$$+1$$$ 的快乐值。

  2. 无糖口味，感觉很一般，雪碧喝完后有 $$$0$$$ 的快乐值。

  3. 樱桃口味，雪碧的噩梦，雪碧喝完后有 $$$-1$$$ 的快乐值。

每天雪碧买完可乐后不一定当天喝完，他可以囤积若干瓶可乐，然后在将来的某一天，把囤积的所有可乐一口气喝完。雪碧一次喝完若干可乐后获得的快乐值为一次喝的所有可乐的快乐值之积。雪碧能得到的快乐值的总和是若干次喝可乐的快乐值之和。

现在雪碧通过魔法获知了未来 $$$n$$$ 天商店的可乐出售情况数组 $$$a$$$，其中 $$$a_i$$$ 代表未来第 $$$i$$$ 天商店出售的可乐的快乐值。他突发奇想，想知道他能否通过囤积和一口气喝完的手段，在把未来 $$$n$$$ 天的所有可乐都喝完后，获得恰好 $$$x$$$ 的快乐值的总和。

乐于思考的雪碧连续想了 $$$q$$$ 个这样的问题，并期待你给他回答。

形式化地，给定长度为 $$$n$$$ 的由 $$$-1, 0, 1$$$ 组成的数组 $$$a$$$，询问是否存在一种方案通过在所有相邻的两数之间填入共 $$$n-1$$$ 个加号和乘号所形成的数学表达式的求值为 $$$x$$$。

Input

第一行一个整数 $$$T$$$ ($$$1\le T\le 10^4$$$)，代表测试用例数。

对于每组测试用例：

  • 第一行两个整数 $$$n,q$$$ ($$$1\le n,q\le 10^6$$$) 分别表示未来天数和询问次数。
  • 第二行 $$$n$$$ 个整数，其中第 $$$i$$$ 个整数 $$$a_i$$$ ($$$a_i\in \{-1,0,1\}$$$) 表示未来第 $$$i$$$ 天商店出售的可乐的快乐值。
  • 接下来 $$$q$$$ 行，每行一个整数 $$$x$$$ ($$$1\le x\le 10^6$$$)，表示雪碧的一个询问。

保证所有测试用例的 $$$n$$$ 之和与 $$$q$$$ 之和均不大于 $$$10^6$$$。

Output

对于每一个询问，如果满足条件则输出一行 Yes，否则输出一行 No。

你可以以任意大小写输出 Yes 和 No（例如，字符串 yEs、yes、Yes 和 YES 将被识别为肯定的回答）。

Example
Input
2
3 2
1 1 0
2
3
3 1
1 0 -1
1
Output
YES
NO
YES
Note

对于第一个测试用例：

  • 显然可以通过方案 $$$1 + 1 + 0 = 2$$$ 得到快乐值 $$$2$$$。

  • 容易证明不存在任何方案得到快乐值 $$$3$$$。

对于第二个测试用例：

  • 可以通过方案 $$$1 + 0 \times -1 = 1$$$ 得到快乐值 $$$1$$$。

I. 小 P 爱折跃
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

有 $$$n$$$ 座城市，分别编号为 $$$1, 2, \dots, n$$$，每座城市持有一台传送到其他城市的折跃门。每台折跃门只能传送到指定编号的城市，且每座城市只能被一台折跃门传送到。给定数组 $$$a$$$，其中 $$$a_i$$$ 表示第 $$$i$$$ 座城市持有的折跃门可以传送到第 $$$a_i$$$ 座城市。

为了加快城市之间的交通速度，市长们委托小 P 为他们进行折跃门的调整，使得从任意一座城市出发，都可以通过折跃门到达任意一座城市。

小 P 可以任意交换两座城市持有的折跃门，他希望知道最少需要交换多少次，才能使得从任意一座城市出发，都可以通过折跃门到达任意一座城市。

Input

第一行一个整数 $$$T$$$ ($$$1 \le T \le 10^4$$$)，表示测试用例数。

对于每个测试用例：

第一行一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$)，表示城市的数量。

第二行共 $$$n$$$ 个整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$)，表示第 $$$i$$$ 座城市持有的折跃门可以传送到第 $$$a_i$$$ 座城市。

保证所有测试用例的 $$$n$$$ 之和不超过 $$$10^5$$$。

Output

对于每个测试用例，输出一行一个整数，表示最少需要交换多少次，才能使得从任意一座城市出发，都可以通过折跃门到达任意一座城市。

Example
Input
5
1
1
2
1 2
3
1 3 2
4
1 3 2 4
5
3 4 5 2 1
Output
0
1
1
2
1
Note

对于第一组测试用例：显然只有一座城市，不需要交换折跃门，因此答案为 $$$0$$$。

对于第三组测试用例：只需交换城市 1 与其它城市中任意一个折跃门即可使任意两座城市互通，因此答案为 $$$1$$$。

J. 好得不能再好了！泰拉投资大师课
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

你是身无分文的博士，今天你看到了泰拉投资大师课的广告，你决定报名这个课程。你想到当年叉烧猫用 $$$20$$$ 龙门币赚了 $$$3700$$$ 万龙门币，今天你博士也要成为投资大师！

投资有风险，入市需谨慎

在一次模拟投资中，你有 $$$p$$$ 的概率赚到钱，有 $$$1-p$$$ 的概率亏钱。

你的目标是赚到 $$$n$$$ 次钱，而你一共有 $$$n-1$$$ 次亏钱的机会，即：当你总共赚了 $$$n$$$ 次钱时，就算完成目标，不需要再继续投资；当你总共亏了 $$$n$$$ 次钱时，就算失败，不需要再继续投资。每次投资的结果是独立事件。

为了评估风险，你想知道，能成功完成目标的概率是多少？

Input

第一行一个整数 $$$T$$$ ($$$1 \le T \le 10^4$$$)，表示测试用例数。

接下来，对于每组测试用例：

一行三个正整数 $$$n, p, q$$$ ($$$1 \le n \le 10^5$$$, $$$1 \le p \lt q \le 10^5$$$)，表示你的目标是赚到 $$$n$$$ 次钱，你有 $$$\frac{p}{q}$$$ 的概率赚钱，$$$1-\frac{p}{q}$$$ 的概率亏钱。

保证所有测试用例的 $$$n$$$ 之和不超过 $$$5 \cdot 10^6$$$。

Output

对于每组测试用例，输出一行一个整数表示答案对 $$$10^9+7$$$ 取模的结果。

Example
Input
3
1 1 2
4 2 5
10086 114 514
Output
500000004
815744006
831515095
Note

$$$\frac{a}{b} \equiv a \cdot b^{m-2} \pmod m$$$，其中 $$$m$$$ 是质数。

对于第一组样例：只有两种方案，第一次失败或者第一次成功。但是因为只能失败 $$$n-1=0$$$ 次，所以达成目标的概率就是 $$$\frac{1}{2} \equiv 500000004 \pmod{10^9 + 7}$$$。

K. 说重话！！！
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

小 A 迷上了一款三字游戏，天天摸鱼并在三字游戏里战斗爽！！！他的 mentor 知道后十分生气，对小 A 说了重话，在小 A 没拿出接下来 $$$n$$$ 天的具体奋斗方案之前，实行一刀切的禁娱计划，不接受任何争议！！！

小 A 的好好师兄牛哥在去上班前给小 A 拟定了一份 $$$m$$$ 项的奋斗清单。清单每行包含两个数字，分别代表奋斗事项类型和从第几天开始。已知对于第 $$$x$$$ 天开始的奋斗事项有：

  • 奋斗事项 1：从 $$$x$$$ 天开始多奋斗 $$$1$$$ 小时，第 $$$x+1$$$ 天多奋斗 $$$2$$$ 小时，第 $$$x+2$$$ 天多奋斗 $$$3$$$ 小时... ，从 $$$x$$$ 天往后的第 $$$k$$$ 天多奋斗 $$$k+1$$$ 个小时，持续到第 $$$n$$$ 天。

  • 奋斗事项 2：从 $$$x$$$ 天开始多奋斗 $$$1$$$ 小时，第 $$$x+1$$$ 天多奋斗 $$$4$$$ 小时，第 $$$x+2$$$ 天多奋斗 $$$9$$$ 小时... ，从 $$$x$$$ 天往后的第 $$$k$$$ 天多奋斗 $$$(k+1)^2$$$ 个小时，持续到第 $$$n$$$ 天。

现请你编写一份程序帮小 A 制定具体的奋斗方案，帮他算出每天需要奋斗多少个小时。由于这个数字可能较大，请输出答案对 $$$10^9+7$$$ 取模后的结果。

Input

第一行一个正整数 $$$T$$$ ($$$1\le T\le 10^4$$$) 表示测试用例数。

对于每组测试用例：

  • 第一行包含一个 $$$n$$$ ($$$1\le n\le 10^5$$$) 和 $$$m$$$ ($$$1\le m\le 10^5$$$)，表示接下来奋斗的天数和牛哥的清单有多少项。

  • 接下来 $$$m$$$ 行，每行包含两个数字 $$$op$$$ ($$$1\le op\le 2$$$) 和 $$$x$$$ ($$$1\le x\le n$$$)，分别表示奋斗事项类型和从第几天开始。

保证所有测试用例的 $$$n$$$ 之和与 $$$m$$$ 之和均不大于 $$$10^5$$$

Output

对于每组测试用例，输出一行 $$$n$$$ 个整数，其中第 $$$i$$$ 个数表示第 $$$i$$$ 天需要奋斗小时数对 $$$10^9+7$$$ 取模后的结果。

Example
Input
2
6 4
1 3
2 1
2 5
1 1
10 2
2 2
2 7
Output
2 6 13 22 34 50
0 1 4 9 16 25 37 53 73 97
Note

我们姑且认为小 A 所在的世界一天有不止 24 个小时。

L. 向日葵的坡道
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
「人啊，幸福吧！不沉溺在幸福中，也不对世界感到绝望，只是幸福地活下去！」
— 路德维希·维特根斯坦

你所看到的世界尽头的天空。

世界之界限的天空。

最尽头的天空。

我能不能够和你一起看呢？

在那里看着同一个世界的终结......

虽然不在同一片天空之下...... 却在同一片天空之下看着......

...... 我不时会思考这样的事情。

在回忆起......

回忆起那片向日葵前方的坡道时。

给定一个有向二分图（一个有向图，所有点可以被分为两类，同一类的点之间不存在边）。已知这个有向二分图的两个独立点集分别为 $$$A$$$ 和 $$$B$$$，且 $$$A$$$ 和 $$$B$$$ 的大小均为 $$$n$$$。

对点进行编号，$$$A$$$ 中的点从 $$$1$$$ 到 $$$n$$$，$$$B$$$ 中的点从 $$$n+1$$$ 到 $$$2n$$$。

在这个图中，所有的边均从 $$$A$$$ 中的某个点指向 $$$B$$$ 中的某个点，且不会有重边。

现在，请你为给定的有向二分图设计一种加边方案，使得该图成为强连通图，且加的边数最少。你只需要输出任意一种满足条件的方案即可。

请注意，不保证输入图连通。不要求加边后的图还是二分图，只要有强连通性质且边数最小即可。

Input

第一行输入一个正整数 $$$T$$$ ($$$1 \leq T \leq 10^4$$$)，表示测试用例数。

对于每组测试用例：

  • 第一行输入两个整数 $$$n$$$ ($$$1 \leq n \leq 10^6$$$) 和 $$$m$$$ ($$$0 \leq m \leq 2\cdot 10^6$$$)， 分别表示有向二分图两个点集的大小和图的边数。
  • 接下来 $$$m$$$ 行，每行输入两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \leq u \leq n, n + 1 \leq v \leq 2\cdot n$$$)，表示有向二分图的一条边， 边的方向是从 $$$A$$$ 中的点 $$$u$$$ 指向 $$$B$$$ 中的点 $$$v$$$。

保证所有测试用例中的 $$$n$$$ 之和不超过 $$$10^6$$$，$$$m$$$ 之和不超过 $$$2\cdot 10^6$$$。

Output

对于每个测试用例，首先输出一行一个整数 $$$k$$$，表示需要添加的边数。

接着输出 $$$k$$$ 行，每行输出两个整数 $$$u$$$ 和 $$$v$$$，表示新增一条从 $$$u$$$ 指向 $$$v$$$ 的边。

如果有多种方案，你只需要输出其中一种合法方案即可。

Example
Input
3
1 0
1 1
1 2
2 3
1 3
1 4
2 3
Output
2
1 2
2 1
1
2 1
2
4 2
3 1
Note

对于第一组样例：

加边前
加边后

此时形成了强连通图。

M. GLLF 砍木棍
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

上回 GLLF 对一个木头砍了 $$$10^{100}$$$ 刀，他感觉有点累了，所以他决定砍一根木棍。

他有一根长度为正整数 $$$n$$$ 的木棍，把它砍成了若干个长度为正整数的小段，他很好奇有多少种砍法能使得这些小段木棍能拼成一个凸多边形。

两种砍法不同当且仅当存在砍的位置不同。我们把每段的长度按顺序放入数组，如长度为 $$$6$$$ 的木棍按顺序砍出 $$$1,2,1,2$$$ 四段，则可以表示为 $$$[1,2,1,2]$$$。两个不同的数组代表不同的砍法。

由于这个问题的答案可能很大，请你将答案对 $$$10^9 + 7$$$ 取模之后输出。

Input

第一行一个正整数 $$$T$$$ ($$$1 \le T \le 10^5$$$)，表示数据组数。

接下来 $$$T$$$ 行，每行一个正整数 $$$n$$$ ($$$3\le n \le 10^9$$$)，表示木棍的长度。

Output

对于每组数据，输出一行一个对 $$$10^9 + 7$$$ 取模之后的整数，表示有多少种砍法。

Example
Input
5
3
4
5
114514
1919810
Output
1
1
8
669267460
159473596
Note

对于第三个测试用例，一种有八种切法：$$$[1,1,1,1,1]$$$, $$$[1,1,1,2]$$$, $$$[1,1,2,1]$$$, $$$[1,2,1,1]$$$, $$$[2,1,1,1]$$$, $$$[1, 2, 2]$$$, $$$[2, 1, 2]$$$, $$$[2, 2, 1]$$$

N. 哥伦比亚大选
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

哥伦比亚（Columbia）是泰拉大陆上最年轻的国家，但发展迅速，富有野心，且因对感染者相对包容的态度而吸引了大量感染者前来谋生。

哥伦比亚街景

哥伦比亚的建立距今并不像其他国家那般遥远，但发展速度却十分惊人，无论是殖民问题还是近十年与不间断的小规模战事都不曾拖慢这个大国的发展速度。

哥伦比亚原先为维多利亚治下西北各城邦的联盟。受高卢入侵的影响，维多利亚无暇顾及这些西北荒原的城市，这也导致了哥伦比亚的独立。之后，哥伦比亚军队击退了边境领公爵的进攻。

哥伦比亚已知有两级行政区域，分别为州级和城市级，城市所属于州。哥伦比亚实行联邦制。国家元首为总统，现任总统为马克·麦克斯，副总统为杰克逊。

近期，哥伦比亚将要进行新一轮的大选，马克·麦克斯将会参加连任。现在给出若干总统候选人，以及他们的支持者数量，你需要找出哪位候选人最受人们支持。我们定义，支持者数量最多的人最受人们支持。

Input

输入的第一行包含一个整数 $$$n$$$ ($$$1\le n \le 10$$$)，表示总统候选人的数量。

接下来 $$$n$$$ 行，每行包含一个只包含大小写字母的字符串 $$$s$$$ ($$$1\le\lvert s \rvert\le 20$$$) 和一个整数 $$$a$$$ ($$$1\le a\le 10^3$$$)，表示一个候选人的名字和他的支持者数量。

保证所有候选人的名字各不相同，且支持者数量各不相同。

Output

输出一行一个字符串，表示最受人们支持的候选人的名字。

Example
Input
7
Keqing 1
LuoXuan 321
XianYa 333
XuFeichi 233
CZY 777
PangXiang 888
MarkMax 1000
Output
MarkMax