这道题是为了让第一次参加程序设计竞赛的同学熟悉比赛规则，我们会对评测规则做一些简单介绍。
传统题 是目前算法竞赛中较为常见的题型。
选手需要提交源代码，评测系统会使用事先准备好一些输入数据和相应的输出数据作为测试点，将选手提交的源代码编译后，让选手程序读入输入数据，通过将选手输出与事先准备好的输出比较，来判断选手程序是否正确。这种评测方式被称之为 黑盒评测。
对于一个测试点，往往还会设置时间限制和空间限制。
时间限制，指的是程序运行时间的限制。选手程序在 一个测试点上的运行时间不能超过给定的时间限制。
空间限制，指的是程序使用的内存量的限制。选手程序在运行时 占用的最大空间不能超过给定的空间限制。
这一过程结束后，评测系统会根据程序的运行状态，给出不同的 评测结果：
- Accepted（AC）：选手程序被接受。
- Compile Error（CE）：选手程序无法正常编译。
- Wrong Answer（WA）：选手程序正常结束，但是选手程序的输出与测试点输出不符。
- Runtime Error（RE）：选手程序非正常结束（选手程序结束时的返回值不为零）。
- Time Limit Exceeded（TLE）：选手程序运行的时间超过了给定的时间限制。
- Memory Limit Exceeded（MLE）：选手程序占用的最大空间超过了给定的空间限制。
在 ICPC 类型赛事中（本次比赛采用该类型），你的程序需要在一道题目的所有测试点上都取得 AC 状态。
—————————————————————————————————————————————————–
车南大学第六届 "帆软杯" 程序设计竞赛开始了！
小 M 被指定为负责统计参赛人数的志愿者，现在四位小组长已经各自报上了每个年级的参赛人数，你能帮小 M 算出总参赛人数吗？
一行 $$$4$$$ 个整数 $$$x_1,x_2,x_3,x_4(0\le x_1, x_2, x_3, x_4\le100)$$$，表示四个年级各自的参赛人数。
输出一行一个整数 $$$t$$$，表示总参赛人数。
99 82 44 35
260
在一场 codeforces 赛制的比赛中，一般有 $$$n$$$ 道题目，每道题目有一个初始的分数 $$$a_i$$$，同时，每道题目还有一个每分钟扣除的分数 $$$b_i$$$ 和最低可以获得的分数 $$$c_i$$$。同时，每次错误的提交都会使得你这题的得分减少 $$$50$$$。也就是说，假如你在第 $$$t$$$ 分钟第 $$$s$$$ 次提交了一道题目并且最终通过，那么你这道题目的得分是 $$$\max(c_i,a_i-b_i\times t-50\times(s-1))$$$；否则，不论你提交了多少次，只要你没有通过这道题目，你的得分就是 $$$0$$$。
现在给你一场 codeforces 比赛的题目信息和 YiYi 的提交信息，请你帮她算算她所有题目最终的分数的总和是多少。
第一行，一个整数 $$$n(1\le n\le 10^3)$$$，代表比赛的题目数量。
第二行，$$$n$$$ 个整数 $$$a_1,\dots,a_n(1\le a_i\le 10^6)$$$，代表每道题的初始分数。
第三行，$$$n$$$ 个整数 $$$b_1,\dots,b_n(1\le b_i\le a_i)$$$，代表每道题每分钟扣除的分数。
第四行，$$$n$$$ 个整数 $$$c_1,\dots,c_n(1\le c_i\le a_i)$$$，代表每道题低可以获得的分数。
接下来的 $$$n$$$ 行，每行给出对应的题目的提交信息，其中第 $$$i$$$ 行代表第 $$$i$$$ 题的提交信息，每行信息这样表示 $$$t_i,s_i(0\le t_i \le 10^3;-10^3\le s_i\le 10^3)$$$。其中 $$$t_i$$$ 代表该题最后一次提交的时间 ；而 $$$s_i$$$ 则代表此次提交是第几次且是否通过：$$$s_i \gt 0$$$ 则代表第 $$$s_i$$$ 次提交通过；$$$s_i\le 0$$$ 则代表未提交或者提交了 $$$-s_i$$$ 次后仍未通过。
输出一个整数，代表 YiYi 在这场比赛中最终的得分。
5 7 1 2 6 5 3 1 2 2 1 3 1 1 4 2 1 1 0 2 0 1 15 -3 11 5
9
6 1 2 3 4 5 6 1 1 1 1 1 1 1 1 1 1 1 1 1 -1 3 -2 0 0 0 0 0 0 0 0
0
7 250 750 1250 3333 4444 5555 6666 1 2 3 4 5 6 7 1 1 1 1 1 1 1 0 1 1000 1 32 2 999 -1000 872 1 12 3 0 0
6822
小M 不久前学会了猫娘魔法，可以将任意人形生物变成可爱的猫娘美少女。
于是，在一个月黑风高的晚上，小D 变成了猫娘。
普通的猫猫叫声是 'meow '。
而 猫娘小D 的叫声是 'moew '。
车南大学的麦克风录下了一段声音，是一长段猫猫或者猫娘的叫声。
你需要根据这段声音找出 小D 是第几位。
一行一个字符串 $$$s$$$，保证 $$$1 \le |s|\le 10^5$$$。
保证 $$$s$$$ 中只包含猫猫或者猫娘的叫声，并且猫娘的叫声有且只有一次出现。
输出一个整数 $$$x$$$，表示小D是第 $$$x$$$ 个声音。
meow~meow~moew~meow~meow~
3
一个长度为 $$$n$$$ 的排列 $$$p$$$ 的得分计算方式如下：
给定一个整数 $$$n$$$，假如你可以任意选择 $$$k$$$，请你求出在所有长度为 $$$n$$$ 的排列中，得分最大的排列的得分是多少。
一个长度为 $$$n$$$ 的排列 $$$p$$$ 是指从 $$$1$$$ 到 $$$n$$$ 的每个整数恰巧在 $$$p$$$ 中出现一次，例如 $$$[3,1,2]$$$、$$$[1]$$$ 都是排列，但是 $$$[1,1,3]$$$、$$$[3,2,4]$$$ 都不是排列。
第一行，一个整数 $$$t(1\le t\le 10^5)$$$，代表数据组数。
对于每组数据，仅输入一个正整数 $$$n(2\le n\le 10^{18})$$$，代表排列的长度。
由于这题输入数据的值比较大，所以你可能需要使用能够表示更大数据的数据类型，例如 C++ 中的 long long。
对于每组数据，输出一个整数，代表在确定 $$$k$$$ 的情况下，长度为 $$$n$$$ 的排列的得分最多是多少。
6 2 3 7 916 5201314114514 1000000000000000000
1 1 2 9 41 59
对于样例第一组数据，选择 $$$k=2$$$，此时得分最高的排列为 $$$[1,{\color{red}2}]$$$，这个排列的得分为 $$$1$$$。
对于样例第三组数据，选择 $$$k=1$$$，此时得分最高的排列为 $$$[2,1,{\color{red}3},{\color{red}6},7,4,5]$$$。
对于 $$$i=2$$$，$$$1\neq 1\times 2$$$，所以这个位置不得分。
对于 $$$i=3$$$，$$$3 = 1\times (2+1)$$$，所以这个位置得分。
对于 $$$i=4$$$，$$$6 = 1\times (2+1+3)$$$，所以这个位置得分。
对于 $$$i=5$$$，$$$7\neq 1\times (2+1+3+6)$$$，所以这个位置不得分。
对于 $$$i=6$$$，$$$4\neq 1\times (2+1+3+6+7)$$$，所以这个位置不得分。
对于 $$$i=7$$$，$$$5\neq 1\times (2+1+3+6+7+4)$$$，所以这个位置不得分。
最终，这个排列的得分为 $$$0+1+1+0+0+0=2$$$。
小 M 是车南大学 J8241 班的班长，学院的辅导员希望小 M 找到一段时间来给全班同学做一次团建活动。
这可难坏了小 M，因为大家的课表几乎是各不相同的。
为了完成这个任务，小 M 将一周的时间分为了 $$$m$$$ 段，接着，她拿到了全班 $$$n$$$ 个同学的时间安排表，每个同学会在时间安排表上写上自己的空闲时间段。
小 M 希望能够找出 $$$1$$$ 段时间举行团建活动，使得在缺席的同学尽可能的少的情况下，尽可能早的进行，你能帮帮小 M 吗？
第一行 $$$2$$$ 个整数 $$$n, m(1\le n,m\le 10^5$$$)，表示同学的个数和时间的段数。
接下来 $$$n$$$ 行，第 $$$i+1$$$ 行先是一个整数 $$$p_i(1\le p_i\le10)$$$，表示这名同学的空闲时间段数。紧接着 $$$2\times p_i$$$ 个整数 $$$l_{i, j}, r_{i,j}(1\le l_{i,1}\le r_{i,1} \lt l_{i,2}\le r_{i,2}\cdots \lt l_{i,p_i}\le r_{i,p_i}\le m)$$$，表示这名同学在 $$$[l_{i,j}, r_{i,j}]$$$ 这一整段时间有空。
$$$1$$$ 行两个整数 $$$t, x$$$，分别表示最早的时间和缺席的人数。
4 10 2 2 6 8 8 1 1 5 3 1 1 3 3 9 9 1 3 7
3 0
在哈尔冰的比赛之后，小M 变成了猫娘。
某个周末在听完计拔基地启动仪式后，她顺手解决了车南大学OJ的问题。
于是，小M 是全能猫娘的消息终于瞒不住了。
各种各样的任务以各种各样的理由加入了 小M 的 TodoList。
为了高效的完成任务，小M 将这个周末的时间划分成了 $$$N$$$ 段。
在这 $$$N$$$ 段时间中 小M 需要完成 $$$M$$$ 项任务，每一项任务有一个耗时 $$$T_i$$$ 和一个 Deadline $$$S_i$$$ (需要恰在 $$$S_i$$$ 时刻或者在 $$$S_i$$$ 时刻之前完成)。
当然，小M 必须在对应的 Deadline 之前完成这项任务。另外，小M 是单线程猫娘，所以她做一项工作会一直做到完成为止。
猫娘当然是喜欢睡懒觉的，她想让你帮她算一算，在 Deadline 的压迫下，她最晚能在什么时候起床。
第 $$$1$$$ 行 $$$2$$$ 个正整数 $$$N,M(1\le N\le 10^7;1\le M\le10^5)$$$，表示时间段的数量和任务数量。
第 $$$1+i$$$ 行 $$$2$$$ 个正整数 $$$T_i,S_i(1\le T_i\le10^5, 1\le S_i\le N)$$$，表示第 $$$i$$$ 个任务的耗时和 Deadline。
第 $$$1$$$ 行一个整数 $$$ans$$$，表示 小M 最晚在 $$$ans$$$ 时刻起床干活可以顺利完成任务。
特别的，如果即使 小M 周末不睡觉 (在 0 时刻便起床开始干活) 也无法顺利在对应的 Deadline 前完成所有任务，那么请输出 -1。
99 4 3 5 8 14 5 20 1 16
2
520 6 1 7 3 6 2 19 2 11 4 23 4 16
3
1314 1 16 7
-1
你是一位国王，在你的手下有 $$$n$$$ 个士兵，$$$m$$$ 支矛和 $$$k$$$ 个盾。同时，每个士兵都有一个生命值 $$$a$$$，每支矛都有一个耐久度 $$$b$$$，每个盾都有一个防御值 $$$c$$$。
现在，你要带领着这群士兵和你的武器去击杀一条恶龙。战斗开始前，你可以给每一个士兵装备最多一支矛和一个盾，当然你也可以给一个士兵只装备一支矛或者只装备一个盾，或者什么都不装备。假如一些矛或一些盾没有被任何士兵装备，那么他们的耐久度和防御值会在战斗前会立刻变成 $$$0$$$。
在战斗时，每一秒中会发生如下事情：
当没有士兵存活时，战斗就结束了。
假如以最优的方式给士兵装备矛和盾，那么恶龙受到的伤害最多是多少。
第一行，一个整数 $$$t(1\le t\le 10^4)$$$，代表数据组数。
对于每组数据：
第一行，三个整数 $$$n,m,k(1\le n,m,k\le 2\cdot10^5)$$$，分别代表士兵的数量，矛的数量和盾的数量。
第二行，$$$n$$$ 个整数 $$$a_1,\dots,a_n(1\le a_i\le 10^9)$$$，代表每一个士兵的生命值。
第三行，$$$m$$$ 个整数 $$$b_1,\dots,b_m(1\le b_i\le 10^9)$$$，代表每一支矛的耐久度。
第四行，$$$k$$$ 个整数 $$$c_1,\dots,c_k(1\le c_i\le 10^9)$$$，代表每一个盾的防御值。
保证同一测试点内的 $$$n,m,k$$$ 的总和都不超过 $$$2\cdot10^5$$$。
对于每组数据，输出一个整数，代表恶龙受到的伤害的最大值。
5 2 2 2 8 1 4 6 1 4 2 2 2 1 1 9 9 1 2 4 1 2 2 1 8 6 999999999 1 9 7 9 5 7 11 9 1 2 18 11 8 13 4 10 1 13 2 10 16 8 9 3 13 12 5 4 1 857487028 773029872 845119807 475685071 988386263 771098833 170131470 947400180 790206795 191652034
10 8 26 74 2678837278
称一个仅由数字构成的长度大于等于 $$$2$$$ 的字符串 $$$s$$$ 是美丽的当且仅当存在一个下标 $$$k$$$，使得 $$$\sum_{i=1}^k s_i=number(s_{k+1}s_{k+2}\dots s_n)$$$。
对于一个仅由数字构成的字符串 $$$t$$$ 来说，$$$number(t)$$$ 等于将 $$$t$$$ 转成一个整数后的值。例如 $$$number("123")=123$$$，$$$number("0109")=109$$$。
字符串 $$$"235"$$$ 是一个美丽的字符串，因为 $$$2+3=number("5")=5$$$；字符串 $$$333413$$$ 也是一个美丽的字符串，选择 $$$k=4$$$，那么 $$$3+3+3+4=number("13")=13$$$。
YiYi 现在有一个长度为 $$$n(n\ge2)$$$ 的仅由数字构成的字符串 $$$s$$$，在每次操作中，她会选择一个下标 $$$i(1\le i\le n)$$$，使得 $$$s_i=c(0\le c\le 9)$$$。在她每一次操作结束后，请你回答，假如可以对字符串 $$$s$$$ 进行任意重新排列，能否使得字符串 $$$s$$$ 成为一个美丽的字符串。
第一行，一个整数 $$$t(1\le t\le 10^4)$$$，代表数据组数。
对于每组数据：
第一行，两个整数 $$$n,q(2\le n \le 5\cdot10^5;1\le q\le 5\cdot 10^5)$$$，代表 YiYi 的数字字符串的长度和操作次数。
第二行，一个长的为 $$$n$$$ 仅有数字构成的字符串 $$$s$$$，代表初始时的字符串。
接下来连续的 $$$q$$$ 行，每行两个整数 $$$pos,c(1\le pos \le n;0\le c\le 9)$$$，代表这一次操作将 $$$s_{pos}$$$ 修改为 $$$c$$$。
保证同一测试点内 $$$n$$$ 和 $$$q$$$ 的总和均不超过 $$$5\cdot 10^5$$$。
在每一次修改结束后，在可以对字符串 $$$s$$$ 进行任意重新排列的情况下，如果能够使得字符串 $$$s$$$ 是美丽的，输出 "YES";否则，输出 "NO"。
你可以以任何大小写形式输出 "YES "和 "NO"（例如，字符串 "yES"、"yes "和 "Yes "都将被视为肯定答案）。
4 4 2 0909 3 9 2 0 3 3 520 3 3 1 1 3 1 2 1 09 1 9 8 5 01230123 3 4 6 6 1 5 2 2 8 3
NO YES YES YES YES YES NO YES YES NO NO
你一张由有向边和无向边组成的图。要求你给所有无向边定向，转为有向边。使得图中没有环。若无解输出 $$$-1$$$ 。
第一行两个正整数 $$$n,m_1,m_2(1\le n,m_1,m_2 \le 2\times 10^5)$$$，分别代表图中的顶点数，无向边的边数和有向边的边数。
后 $$$m_1$$$ 行，第 $$$i$$$ 行两个正整数 $$$u_i,v_i(1\le u_i,v_i\le n;u_i\neq v_i)$$$ 表示存在一条连接 $$$u_i$$$ 和 $$$v_i$$$ 的无向边。
后 $$$m_2$$$ 行，第 $$$i$$$ 行两个正整数 $$$x_i,y_i(1\le x_i,y_i\le n;x_i\neq y_i)$$$ 表示存在一条从$$$x_i$$$ 到 $$$y_i$$$ 的有向边。
保证图中不存在重边或自环。
无解：输出 $$$-1$$$ 。
有解：输出 $$$m_1$$$ 行，每行两个正整数 $$$u_i',v_i'$$$ 表示第 $$$i$$$ 条无向边被定向为了 $$$u_i'$$$ 到 $$$v_i'$$$ 的有向边。
若有多组解，你只需输出任意一种即可。
6 3 5 4 5 3 5 2 3 1 2 1 3 2 4 2 5 1 5
5 4 3 5 3 2
6 3 5 4 5 3 5 2 3 1 2 1 3 2 4 2 5 5 1
-1
给定一个由小写字母和 $$$?$$$ 组成的字符串，$$$?$$$ 可以表示任意小写字母。你需要是将这个字符串分割成尽可能少的回文子串。求出最少可以分割成多少个回文子串，并计算填充所有 $$$?$$$ 后再分割的方案数，两种方案不同当且仅当填充 $$$?$$$ 的方式不同或者划分序列的方式不同。最终的分割方案数需要对 $$$998244353$$$ 取模后输出。
对于两个长度均为 $$$k$$$ 的分割序列 $$$[s_1,s_2,\dots,s_k]$$$ 和 $$$[t_1,t_2,\dots,t_k]$$$ 来说，称它们不同当且仅当存在一个下标 $$$i(1\le i\le k)$$$，使得 $$$s_i\neq t_i$$$。
对于一个长度为 $$$n$$$ 的字符串 $$$s$$$ 来说，$$$s$$$ 的一个子串为存在两个下标 $$$l,r(1\le l\le r\le |s|)$$$，那么 $$$s_l\dots s_r$$$ 就是 $$$s$$$ 的一个子串。例如字符串 $$$"abc"$$$ 的子串有 $$$"a","b","c","ab","bc","abc"$$$，但是 $$$"ac","cb","ba","d"$$$ 都不是字符串 $$$"abc"$$$ 的子串。
如果一个字符串从前向后读和从后向前读得到的序列是一样的，那么这个字符串就是一个回文串。例如，$$$"madam"$$$ 和 $$$"racecar"$$$ 都是回文串，但是 $$$"love"$$$ 和 $$$"seu"$$$ 都不是回文串。
对于 $$$k$$$ 个字符串 $$$[s_1,s_2,\dots,s_k]$$$ 来说，把它们按顺序拼接起来得到的结果为 $$$s_1+s_2+\dots+s_k$$$，例如 $$$"a"+"bb"+"ccc"="abbccc"$$$。
第一行，一个整数 $$$t(1\le t\le 5000)$$$，代表数据组数。
对于每组数据：
第一行，一个整数 $$$n(1\le n \le 5000)$$$，代表字符串的长度。
第二行，一个长度为 $$$n$$$ 的仅由小写字母和 $$$?$$$ 组成的字符串 $$$s$$$。
保证同一测试点内 $$$n$$$ 的总和不超过 $$$5000$$$。
对于每组数据，输出共两行。第一行，两个整数 $$$k,c(1\le k\le n;0\le c\le 998244352)$$$，代表拆分出的字符串的数量和在把字符串拆分成 $$$k$$$ 部分的且填充所有 $$$?$$$ 情况下，划分方案数是多少；第二行 $$$k$$$ 个用空格隔开的字符串 $$$s_1,\dots,s_k$$$，代表拆分出的字符串，需要满足这些字符串全都是回文串且 $$$s_1+\dots+s_k=s$$$，输出任意一种合法的划分方案即可。
任何满足题目要求的答案都是正确的。
4 5 lyljl 5 ?yj?y 6 aazzaa 7 aa??zaa
3 2 l y ljl 1 1 yyjyy 1 1 aazzaa 1 26 aazazaa
上个月 小M，小D 和 小J 代表车南大学去哈尔冰参加中国汽车性能大赛（China Car Performance Competition），可怜的小 M 在睡觉前忘了开暖气......
醒来的时候，小 M 发现自己已经变成猫娘美少女了。
装作什么都不知道的小 M 去赛场准备参赛时毫无疑问地被志愿者轰了出去，毕竟车南大学提供的选手名单中并没有任何一只兽耳娘。
为了避免 小D 和 小J 发现在没有自己拖累的前提下他俩可以随便拿金的事实，小M 必须要尽快找到车南大学的比赛位置。
比赛场地可以被视作一个无限大的二维平面，车南大学的比赛场地位于 $$$(0,1),(0,-1),(1,0),(-1,0)$$$ 这四个位置中的一个。
作为一只猫娘，小M 已经成功潜入了比赛场地，她现在位于 $$$(0,0)$$$。
然而，刚刚成为猫娘的 小M 没有完美的掌握潜行技能，她只能悄无声息的进行 $$$m$$$ 种不同的移动。
第 $$$i$$$ 种移动可以描述为 $$$(x_i,y_i)$$$，可以在正反两个方向进行，执行这种移动一次后，如果移动前她位于 $$$(x_0,y_0)$$$，则移动后她会位于 $$$(x_0+x_i,y_0+y_i)$$$ 或者 $$$(x_0-x_i,y_0-y_i)$$$。
小M 希望去车南大学的四个可能的比赛场地看一下，请你告诉她，她能否悄无声息地去到这四个位置中的每一个。
本题有多组测试数据。
最开始一行是 $$$1$$$ 个正整数 $$$T(1\le T\le 10^2)$$$，表示测试点的个数。
接下来每个测试点的数据格式如下：
第一行 $$$1$$$ 个正整数 $$$m(1\le m\le10^2)$$$，表示 小M 可以悄无声息的进行的移动的种类数。
第 $$$1+i$$$ 行两个整数 $$$x_i,y_i(-100\le x_i,y_i\le 100)$$$，描述这个移动。
一共 $$$T$$$ 行，第 $$$i$$$ 行表示第 $$$i$$$ 个测试点的答案，如果 小M 能够到达所有的四个可能位置，则输出 "YES"，否则输出 "NO"。
2 3 1 0 0 1 -2 -1 5 3 4 -3 -6 2 -2 5 6 -1 4
YES NO
其实本来移动是单向的，但是单向移动真的太难了所以 小M 喵决定改成双向移动。快说 "谢谢 小M 喵"。