题目背景描述了此题 idea 的来源，跳过此部分不影响做题。
彭彭负责管理车南大学的一些群聊，她写了一个自动审核插件，用来自动审核新入群的成员。
新入群的群成员需要提供自己的姓名和一卡通号，插件会自动检查姓名和一卡通号的格式是否合法，如果合法，就自动通过审核。否则拒绝入群并发送一条消息，告知用户一卡通号格式错误。该用户以后进入人工审核通道。
于是，她写出来的正则表达式长这样：
车南大学的一卡通号是 9 位数字，其中前两位 '21' 是神秘代码，第三位是类型代码，第四到五位是年份代码，剩下四位是编号代码，具体的：
- 前两位 '21' 保持不变，代表车南大学。
- 第三位，'3' 代表本科生，'4' 代表研究生。
- 第四到五位，'24' 代表 2024 年入学，'25' 代表 2025 年入学，以此类推。
- 第六到九位，是入学序号，从 0001 开始，以此递增，最高 9999。
- 前两位固定为 '21'。
- 第三位是 '3' 或 '4'。
- 第四到五位年份字段不做限制。
- 后四位入学序号字段不能全为零。
给你一个一卡通号，你需要判断它是否合法，如果合法，输出 'YES'，否则输出 'NO'。
输入一行字符串，包含一个九位数字一卡通号。
输出一行，包含一个字符串，表示一卡通号是否合法。大小写敏感
213240001
YES
203240001
NO
213240000
NO
在公元四世纪的欧洲有两个帝国，一个在西北方向，另一个在东南方向，两个部落之间被一条河流隔开。这片土地是一个网格图，每片土地只能被任意一个帝国占有或者是河流。具体而言，使用数字 $$$1$$$ 代表被第一个帝国占有的土地，使用数字 $$$2$$$ 代表被第二个帝国占有的土地，数字 $$$0$$$ 代表河流，河流不属于任何一个帝国的土地。这片土地被使用的规则如下：
- 两个帝国的土地必须被河流完全隔开，即两片帝国的土地不能有公共边或者公共点（这很严重，不然会引发战争）。
- 任意一片第一个帝国的土地的西方（地图左侧）和北方（地图上侧）的土地只能是第一个帝国的土地。
- 任意一片第二个帝国的土地的东方（地图右侧）和南方（地图下侧）的土地只能是第二个帝国的土地。
- 任意一片是河流的土地的的西方（地图左侧）和北方（地图上侧）的土地只能是河流或者是第一个帝国的土地，东方（地图右侧）和南方（地图下侧）的土地只能是河流或者是第二个帝国的土地。
合法的土地使用方案 
不合法的土地使用方案 给你一张只由数字 $$$0,1,2$$$ 和 '?' 组成的地图，'?' 代表不知道当前这片土地是什么，请你求出有多少种使用数字 $$$0,1,2$$$ 填充所有 '?' 的方法，满足这篇土地的使用规则。因为方案数可能很多，请在输出方案数量时对于 $$$998244353$$$ 取模。
第一行，一个整数 $$$t(1\le t\le 10^4)$$$，代表数据组数。
对于每组数据：
第一行，两个整数 $$$n,m(1\le n,m\le 4\cdot 10^4)$$$，分别代表地图的长和宽。
接下来连续的 $$$n$$$ 行，每行一个长度为 $$$m$$$ 的字符串，字符串的每个字符 $$$c\in\{0,1,2,?\}$$$，代表当前的地图。
保证同一测试点内的 $$$\bf{n\times m}$$$ 的总和不超过 $$$4\cdot 10^4$$$。
对于每组数据，输出一行数字，代表合法填充当前地图中所有的 '?' 的方案数，将结果对于 $$$998244353$$$ 取模。
6 1 1 ? 1 2 1? 3 3 11? ??? ?22 8 10 1111110002 1111000002 111?????22 111??????? 11???????2 ?????????? ????0?2222 0000222222 3 4 1102 1102 0022 2 2 ?? ??
3 2 4 3100 0 11
简单版和困难版的唯一区别是对于 $$$n,q$$$ 的限制条件不同，在简单版中 $$$\sum n\le 1000;\sum q\le 1000$$$。
Le perdant doit céder le terrain!
在公元四世纪的欧洲，有两个国王A和B，他们都很喜欢数学，所以它们就以66座城池为赌约，来进行一个游戏。游戏的内容如下。
有 $$$n$$$ 个正整数 $$$\{a_1,\dots,a_n\}$$$，在每次操作中，国王必须选择任意一个大于 $$$1$$$ 的正整数 $$$a_i$$$ 和及其一个大于 $$$1$$$ 的因子 $$$x$$$，使得 $$$a_i:=\frac{a_i}{x}$$$。显然当所有数字都变成 $$$1$$$ 时就无法进行任何操作，那么此时当前将要进行操作的国王获得游戏的胜利。且在每轮游戏中由国王A先进行操作，国王B后进行操作，两人轮流操作。
为了进行游戏，国王B拿来了一个数组 $$$[b_1,\dots,b_n]$$$ 并且和国王A商议后决定在每次都在数组 $$$b$$$ 的某一个子段 $$$[b_l,\dots,b_r]$$$ 上进行游戏。不过因为是国王B拿来的数组，在游戏前，国王A可以选择这个子段的某一个非空子序列来作为最终的游戏数组。对于即将进行游戏的某一个子段而言，他有多少种不同的选择非空子序列的方法，使得他可以赢得最终的游戏胜利。
由于选取子序列的方法数量很多，所以在输出答案时，请对 $$$998244353$$$ 取模。
子段是指数组中连续的元素序列，子序列是指从数组中按顺序选取的元素序列，但不要求连续。
对于两个子序列来说，称它们是不同的当且仅当它们的长度不同或者存在任意一个位置，使得这个位置在原数组中的下标不同。
第一行，一个整数 $$$t(1\le t\le 1000)$$$，代表数据组数。
对于每组数据：
第一行，两个整数 $$$n,q(1\le n \le 1000;1 \le q\le 1000)$$$，代表国王B取来的数组长度和游戏次数。
第二行，$$$n$$$ 个整数 $$$b_1,\dots,b_n(1\le b_i\le 10^7)$$$，代表国王B取来的数组。
接下来连续的 $$$q$$$ 行，每行两个整数 $$$l,r(1\le l\le r\le n)$$$，代表当前这次游戏在子段 $$$[b_l,\dots,b_r]$$$ 上进行。
保证同一测试点内 $$$n$$$ 的总和不超过 $$$1000$$$ 且 $$$q$$$ 的总和不超过 $$$1000$$$。
对于每次询问，输出一行整数，代表国王A选取使得他自己能够赢得游戏的非空子序列的方案数，对于 $$$998244353$$$ 取模后的结果。
1 8 10 1 1 4 16 2 8 3 7 1 2 1 5 5 6 2 5 1 8 2 7 3 8 6 8 5 8 3 6
3 27 2 13 223 55 55 5 11 13
简单版和困难版的唯一区别是对于 $$$n,q$$$ 的限制条件不同，在困难版中 $$$\sum n\le 10^6;\sum q\le 10^6$$$。
Le perdant doit céder le terrain!
在公元四世纪的欧洲，有两个国王A和B，他们都很喜欢数学，所以它们就以66座城池为赌约，来进行一个游戏。游戏的内容如下。
有 $$$n$$$ 个正整数 $$$\{a_1,\dots,a_n\}$$$，在每次操作中，国王必须选择任意一个大于 $$$1$$$ 的正整数 $$$a_i$$$ 和及其一个大于 $$$1$$$ 的因子 $$$x$$$，使得 $$$a_i:=\frac{a_i}{x}$$$。显然当所有数字都变成 $$$1$$$ 时就无法进行任何操作，那么此时当前将要进行操作的国王获得游戏的胜利。且在每轮游戏中由国王A先进行操作，国王B后进行操作，两人轮流操作。
为了进行游戏，国王B拿来了一个数组 $$$[b_1,\dots,b_n]$$$ 并且和国王A商议后决定在每次都在数组 $$$b$$$ 的某一个子段 $$$[b_l,\dots,b_r]$$$ 上进行游戏。不过因为是国王B拿来的数组，在游戏前，国王A可以选择这个子段的某一个非空子序列来作为最终的游戏数组。对于即将进行游戏的某一个子段而言，他有多少种不同的选择非空子序列的方法，使得他可以赢得最终的游戏胜利。
由于选取子序列的方法数量很多，所以在输出答案时，请对 $$$998244353$$$ 取模。
子段是指数组中连续的元素序列，子序列是指从数组中按顺序选取的元素序列，但不要求连续。
对于两个子序列来说，称它们是不同的当且仅当它们的长度不同或者存在任意一个位置，使得这个位置在原数组中的下标不同。
第一行，一个整数 $$$t(1\le t\le 1000)$$$，代表数据组数。
对于每组数据：
第一行，两个整数 $$$n,q(1\le n \le 10^6;1 \le q\le 10^6)$$$，代表国王B取来的数组长度和游戏次数。
第二行，$$$n$$$ 个整数 $$$b_1,\dots,b_n(1\le b_i\le 10^7)$$$，代表国王B取来的数组。
接下来连续的 $$$q$$$ 行，每行两个整数 $$$l,r(1\le l\le r\le n)$$$，代表当前这次游戏在子段 $$$[b_l,\dots,b_r]$$$ 上进行。
保证同一测试点内 $$$n$$$ 的总和不超过 $$$10^6$$$ 且 $$$q$$$ 的总和不超过 $$$10^6$$$。
对于每次询问，输出一行整数，代表国王A选取使得他自己能够赢得游戏的非空子序列的方案数，对于 $$$998244353$$$ 取模后的结果。
1 8 10 1 1 4 16 2 8 3 7 1 2 1 5 5 6 2 5 1 8 2 7 3 8 6 8 5 8 3 6
3 27 2 13 223 55 55 5 11 13
无趣的书呆子、讨人厌的优等生，好的坏的都来自于她。十六行诗从未写出任何一句真正的诗，她也从未见过真正的世界。
十六行诗不会写诗，她让 LLM 帮忙生成了 $$$n$$$ 句诗，每句诗有一个特定的韵脚 $$$a_i$$$。
十六行诗认为，只有满足 AABB, ABAB, ABBA 这三种形式韵脚的诗才是真正的诗（A，B 可以相同）。
十六行诗可以从生成的 $$$n$$$ 句诗中删去一些句子，使得剩下的句子，连续的按照每四句一组划分为一首诗，每首诗都能满足上述三种形式之一。
十六行诗想知道，她尽可能少的删去句子后，剩下的句子，能构成多少首诗。
第一行一个整数 $$$n(1\le n \le 500)$$$，表示生成的诗一共有 $$$n$$$ 句。
第二行 $$$n$$$ 个整数，第 $$$i$$$ 个整数表示第 $$$i$$$ 句诗的韵脚 $$$a_i(1\le a_i\le 10^9)$$$。
输出一个整数，表示十六行诗最多能构成多少首诗。
14 1 1 1 1 2 1 1 3 2 4 5 4 5 5
3
15 2 3 1 2 3 2 3 1 1 3 2 2 1 3 3
3
8 1 1 1 2 2 1 3 3
1
Yuhina City 是一个 $$$n$$$ 个点 $$$m$$$ 条边的无向连通图。
现在有一些含有辐射的废料在城市的一些节点处泄露了，废料的辐射值会随着距离递减，即假如节点 $$$i$$$ 有一个辐射值为 $$$r_i$$$ 的废料，那么假如节点 $$$j$$$ 和节点 $$$i$$$ 的最短距离为 $$$d$$$，那么节点 $$$j$$$ 的辐射值为 $$$\max(0,r_i-d)$$$。假如一个点被多个废料影响，那么这个点的辐射值取最高的那个。
作为 Yuhina，你需要把救灾物资从节点 $$$u$$$ 送到另一个节点 $$$v$$$，同时你有一件抗辐射服，最多可以抵挡 $$$k$$$ 次你在某个节点受到的辐射，那么你需要承受的辐射的最小值是多少。
即假如有一条从 $$$u$$$ 到 $$$v$$$ 的路径，经过的节点的辐射值为 $$$r_u,r_a,r_b,\dots,r_v$$$，并且你的抗辐射服可以抵挡 $$$k$$$ 次你在某个节点受到的辐射，那么将这些节点的辐射值从大到小排序后，你需要承受的辐射值为其中第 $$$k+1$$$ 大的数字。假如这条路径上经过的节点数小于等于 $$$k$$$ 个，那么你需要承受的辐射值就是 $$$0$$$。
第一行，一个整数 $$$t(1\le t\le 10^4)$$$，代表数据组数。
对于每组数据：
第一行，三个整数 $$$n,m,q(2\le n\le 10^5;n-1\le m\le 2\cdot 10^5;1\le q\le 5)$$$，代表 Yuhina City 的节点数、连接这些节点的边数和你需要运送救灾物资的次数。
第二行，$$$n$$$ 个整数 $$$r_1,\dots,r_n(0\le r_i\le 10^{14})$$$，代表每个点泄露的核废料的辐射值，假如 $$$r_i=0$$$，代表这个点没有核废料泄露。
接下来的 $$$m$$$ 行，每行三个整数 $$$u,v,w(1\le u,v\le n,u\neq v;1\le w\le 10^9)$$$，代表节点 $$$u$$$ 和 $$$v$$$ 被一条长度为 $$$w$$$ 的无向边连接。
接下来的 $$$q$$$ 行，每行三个整数 $$$u,v,k(1\le u,v\le n,u\neq v;0\le k\le n)$$$，代表运送物资的起点和终点以及抗辐射服可以最多抵挡的辐射次数。
保证同一测试点 $$$n$$$ 的总和不超过 $$$10^5$$$ 且 $$$m$$$ 的总和不超过 $$$2\cdot 10^5$$$。对于 $$$q$$$ 的总和没有额外约束。
对于每次询问，输出一行整数，代表在这次运输救灾物资的过程中，需要承受的辐射的最小值。
2 3 2 4 0 10 0 1 2 9 2 3 10 1 3 0 1 3 1 1 3 2 1 3 3 6 10 5 5 0 11 15 11 0 2 1 8 3 1 3 3 4 1 5 1 3 6 2 1 2 6 3 6 5 4 3 2 6 4 6 9 1 6 4 2 1 3 5 2 1 2 4 1 1 6 0 3 4 0
10 1 0 0 0 8 8 11 15
Syl 有一个长度为 $$$n$$$ 的整数序列 $$${a_i}$$$，她每次可以选择一个下标 $$$i(1 \le i \le n)$$$，并从下列三种操作选择一种进行：
- 将 $$$a_i$$$ 变为 $$$a_i+1$$$ 或 $$$a_i-1$$$。
- 对所有 $$$j \gt i$$$ 且 $$$a_j \gt a_i$$$ 的 $$$j$$$，将 $$$a_j$$$ 变为 $$$a_j-1$$$。
- 对所有 $$$j \lt i$$$ 且 $$$a_j \lt a_i$$$ 的 $$$j$$$，将 $$$a_j$$$ 变为 $$$a_j+1$$$。
现在 Syl 觉得她的序列太不整齐了，于是想通过上面三种操作将序列的所有数字变得相同。请你帮助她算一算，最少需要多少次操作才能满足 Syl 的愿望呢？
第一行，一个整数 $$$t$$$ $$$(1\le t\le 10^5)$$$，表示测试数据的组数。
对于每组测试数据，第一行输入一个整数 $$$n$$$ $$$(1\le n\le 10^5)$$$，表示序列长度；第二行包含 $$$n$$$ 个整数 $$$a_i$$$ $$$(-10^9\le a_i \le 10^9)$$$。
保证所有测试数据的 $$$n$$$ 之和 $$$\sum n\le 10^5$$$。
对每组测试数据，输出一个整数，表示最少能使得序列数字全部相同的操作数。
2 5 1 2 3 4 5 5 5 4 3 2 1
4 6
植树节到了，Syl 整装待发，准备种出一棵美丽的树。
Syl 对美丽的树是有着独到的要求的，她认为一棵有着编号为 $$$1\sim n$$$ 的 $$$n$$$ 个节点的树是美丽的，当且仅当这棵树满足 Syl 给出的 $$$m$$$ 个条件，其中每个条件形如 $$$(v,x,p=0/1)$$$，表示编号为 $$$1$$$ 的点与编号为 $$$v$$$ 的点之间至多/至少距离 $$$x$$$ 条边。
具体来说：
- 如果一个条件是 $$$(v,x,0)$$$，则表示 $$$1$$$ 和 $$$v$$$ 之间至多要距离 $$$x$$$ 条边，即 $$$\mathrm{dis}(1,v)\le x$$$；
- 如果一个条件是 $$$(v,x,1)$$$，则表示 $$$1$$$ 和 $$$v$$$ 之间至少要距离 $$$x$$$ 条边，即 $$$\mathrm{dis}(1,v)\ge x$$$。
请你告诉 Syl，要怎样种出一棵美丽的树呢？如果不存在满足条件的树，这代表 Syl 不再能种出美丽的树，请输出 'Ugly'。
请回顾：一棵大小为 $$$n$$$ 的树是一个有 $$$n$$$ 个节点，$$$n-1$$$ 条边的连通无向图，并且其中任意两个节点之间有且仅有一条简单路径。
第一行，一个整数 $$$t$$$ $$$(1\le t\le 10^5)$$$，表示测试数据的组数。
对于每组测试数据，第一行输入两个整数 $$$n,m$$$ $$$(2\le n\le 2\cdot 10^5, 1\le m \le 2\cdot 10^5)$$$，表示树的大小和条件数量。
对于同一组测试数据接下来的 $$$m$$$ 行，每行包括三个整数 $$$v,x,p$$$ $$$(2\le v\le n, 1\le x\le n-1, p\in\{0,1\})$$$，表示一个条件。
保证所有测试数据的 $$$n$$$ 之和与 $$$m$$$ 之和都不超过 $$$2\cdot 10^5$$$，即 $$$\sum n,\sum m\le 2\cdot10^5$$$。
对于每组测试数据，如果存在方案，先输出 'Beautiful'，然后输出 $$$n-1$$$ 行，每行两个整数 $$$u,v$$$，表示树的一条边 $$$(u,v)$$$。如果不存在满足条件的方案，输出 'Ugly'。
4 5 4 2 3 0 3 2 1 4 1 0 5 3 1 5 4 2 1 0 3 2 1 4 1 0 5 4 1 5 6 2 2 0 2 2 1 3 2 0 3 1 1 4 3 0 5 4 1 6 4 2 1 0 3 1 0 4 3 1 6 4 1
Beautiful 1 4 4 2 4 3 3 5 Ugly Beautiful 1 3 3 2 2 4 4 5 Beautiful 1 2 1 3 2 5 5 4 4 6
在随后的一个世纪里，发生了许多事件，包含以下两种类型：
- 1 $$$x$$$ $$$a$$$：城邦 $$$x$$$ 的特征值变为了 $$$a$$$。
- 2 $$$u$$$ $$$v$$$ $$$k$$$ $$$u_i$$$ $$$v_i$$$：在假设 $$$k$$$ 对城邦之间的边被断开的情况下，城邦 $$$u$$$ 和 $$$v$$$ 之间的最短距离是多少（这些边并没有真的被断开）。
第一行，一个整数 $$$t(1\le t \le 10^4)$$$，代表数据组数。
对于每组数据：
第一行，两个整数 $$$n,q(2\le n\le 10^5;1\le q\le10^5)$$$，分别代表城邦的数量和事件的数量。
第二行，$$$n$$$ 个整数 $$$a_1,a_2,\dots,a_n(1\le a_i\le 10^8)$$$，代表初始时每个城邦的特征值。
接下来连续的 $$$q$$$ 行，每行一个事件。先输入一个整数 $$$op(1\le op\le 2)$$$，代表事件的类型。如果 $$$op=1$$$，则接下来输入两个整数 $$$x,a(1\le x\le n;1\le a\le 10^8)$$$，代表把城邦 $$$x$$$ 的特征值修改为 $$$a$$$。如果 $$$op=2$$$，则接下来首先输入两个整数 $$$u,v(1\le u,v \le n,u\neq v)$$$，代表当前查询最短距离的两个城邦编号。接下来一个整数 $$$k({\bf{0\le k\le \min(9,n-2)}})$$$，代表在这次查询中被断开的边的数量，接下来有 $$$k$$$ 对互不相同的整数对 $$$u_i,v_i(u_i\neq v_i)$$$，代表在当且查询中城邦 $$$u_i,v_i$$$ 之间的边被断开。
保证同一测试点内 $$$n$$$ 和 $$$q$$$ 的总和均不会超过 $$$10^5$$$。
对于每种类型为 $$$2$$$ 的事件，输出一行整数代表答案。
可以证明的是，在题目给定的条件下，任意两对城邦之间都是相互联通的。
3 2 4 1 1 2 1 2 0 1 1 2 1 2 3 2 1 2 0 3 5 1 2 3 2 1 2 1 1 2 2 1 2 1 1 3 2 1 2 1 2 3 1 1 6 2 1 2 1 1 2 6 10 1 1 1 1 9 2 2 1 6 4 1 2 1 3 1 4 1 6 1 1 4 1 2 10 1 3 8 2 3 2 1 2 3 1 4 100000000 2 2 6 0 1 6 9 2 2 6 1 3 1 2 3 5 3 3 5 1 3 1 5
1 2 3 1 1 5 3 2 2 8 17
有一个 $$$n\times n$$$ 的二维数组，其中每个数都是 $$$0$$$ 到 $$$n$$$ 的整数，请你至多修改数组中的 $$$\lfloor \frac{n\times n}{2}\rfloor$$$ 个数，将其改为另一个 $$$0$$$ 到 $$$n$$$ 的整数。所有修改操作完成后，使得数组每一行、每一列的所有数字的 MEX 值都等于一个相同的数字。
MEX 是指所有数字中最小的未出现的非负整数，例如 $$$MEX(\{1,2,3\})=0$$$、$$$MEX(\{1,0,5,7,4,1\})=2$$$ 和 $$$MEX(\{0,0,1,1,1,3\})=2$$$。
$$$\lfloor x\rfloor$$$ 代表对于 $$$x$$$ 向下取整，例如 $$$\lfloor \frac{1}{2} \rfloor=0$$$ 、 $$$\lfloor \frac{9}{2} \rfloor=4$$$ 和 $$$\lfloor \frac{16}{2} \rfloor=8$$$。
第一行，一个整数 $$$t(1\le t\le 10^4)$$$，代表数据组数。
对于每组数据：
第一行，一个整数 $$$n(1\le n\le 1000)$$$，代表二维数组的大小。
接下来的 $$$n$$$ 行，每行 $$$n$$$ 个数字，第 $$$i$$$ 行第 $$$j$$$ 列的数字 $$$a_{i,j}(0\le a_{i,j}\le n)$$$ 代表数组中第 $$$i$$$ 行第 $$$j$$$ 列的数字。
保证同一测试点内的 $$$n^2$$$ 的总和不超过 $$$10^6$$$。
对于每组数据，输出一个 $$$n\times n$$$ 的矩阵，代表修改后的矩阵，矩阵每行每列的 MEX 值需要相同。
可以被证明的是，在题目要求的条件下，一定存在一种修改数组的方案，满足题目的要求。
4 1 1 3 0 1 2 1 2 0 2 1 3 4 1 2 0 2 4 0 4 0 0 1 0 0 3 0 4 1 2 2 2 0 2
1 0 1 2 1 2 0 2 0 1 1 2 0 2 2 0 1 0 0 1 0 2 2 0 2 1 2 2 1 2
简单版和困难版的区别仅在于简单版对于数组 $$$x$$$、$$$y$$$ 和 $$$z$$$ 有额外约束，在简单版中所有的 $$$x_i=1$$$，所有的 $$$y_i=z_i=0$$$。
有一个长度为 $$$n$$$ 的数组 $$$a$$$ 和三个长度为 $$$n$$$ 的数组 $$$x,y,z$$$，$$$a$$$ 中的所有数字都是 $$$1$$$ 到 $$$n$$$ 的正整数。同时，还有一个长度为 $$$m(m\le n)$$$ 的数组 $$$b$$$，初始时数组 $$$b$$$ 中的所有元素都是 $$$0$$$。你的初始得分 $$$score$$$ 为 $$$0$$$。
你需要从左到右遍历数组 $$$a$$$，并且在你遍历到第 $$$i$$$ 个数字 $$$a_i$$$ 时：
- 假如数字 $$$a_i$$$ 在数组 $$$b$$$ 中，你的得分 $$$score$$$ 增加 $$$x_i$$$。
- 否则，你的得分 $$$score$$$ 扣除 $$$y_i$$$。接下来，你可以选择一个位置 $$$j(1\le j\le m)$$$，将数组 $$$b$$$ 中第 $$$j$$$ 个数字 $$$b_j$$$ 替换为 $$$a_i$$$ 并且使你的得分扣除 $$$z_i$$$（或者不进行替换操作）。
在遍历完所有数字后，你的得分 $$$score$$$ 的最大值是多少？
第一行，一个整数 $$$t(1\le t\le 100)$$$，代表数据组数。
对于每组数据：
第一行，两个整数 $$$n,m(1\le m\le n\le 800)$$$，分别代表数组 $$$a$$$ 的长度和数组 $$$b$$$ 的长度。
第二行，$$$n$$$ 个整数 $$$a_1,\dots,a_n(1\le a_i\le n)$$$，代表数组 $$$a$$$。
第三行，$$$n$$$ 个整数 $$$x_1,\dots,x_n(x_i=1)$$$，代表数组 $$$x$$$。
第四行，$$$n$$$ 个整数 $$$y_1,\dots,y_n(y_i=0)$$$，代表数组 $$$y$$$。
第五行，$$$n$$$ 个整数 $$$z_1,\dots,z_n(z_i=0)$$$，代表数组 $$$z$$$。
保证同一测试点内 $$$n$$$ 的总和不超过 $$$800$$$。
对于每组数据，输出一个整数 $$$score$$$，代表在最优替换方案下你的得分的最大值。
7 2 2 1 2 1 1 0 0 0 0 5 2 1 2 2 2 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 6 2 1 2 3 4 5 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 10 3 1 2 3 2 1 4 1 2 4 3 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 5 1 6 1 5 5 9 7 7 8 8 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 2 3 7 1 6 3 10 4 3 1 2 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 1 1 2 1 2 1 2 1 2 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 3 1 5 4 3 5
简单版和困难版的区别仅在于简单版对于数组 $$$x$$$、$$$y$$$ 和 $$$z$$$ 有额外约束，在困难版中对于三个数组中的值没有额外约束。
有一个长度为 $$$n$$$ 的数组 $$$a$$$ 和三个长度为 $$$n$$$ 的数组 $$$x,y,z$$$，$$$a$$$ 中的所有数字都是 $$$1$$$ 到 $$$n$$$ 的正整数。同时，还有一个长度为 $$$m(m\le n)$$$ 的数组 $$$b$$$，初始时数组 $$$b$$$ 中的所有元素都是 $$$0$$$。你的初始得分 $$$score$$$ 为 $$$0$$$。
你需要从左到右遍历数组 $$$a$$$，并且在你遍历到第 $$$i$$$ 个数字 $$$a_i$$$ 时：
- 假如数字 $$$a_i$$$ 在数组 $$$b$$$ 中，你的得分 $$$score$$$ 增加 $$$x_i$$$。
- 否则，你的得分 $$$score$$$ 扣除 $$$y_i$$$。接下来，你可以选择一个位置 $$$j(1\le j\le m)$$$，将数组 $$$b$$$ 中第 $$$j$$$ 个数字 $$$b_j$$$ 替换为 $$$a_i$$$ 并且使你的得分扣除 $$$z_i$$$（或者不进行替换操作）。
在遍历完所有数字后，你的得分 $$$score$$$ 的最大值是多少？
第一行，一个整数 $$$t(1\le t\le 100)$$$，代表数据组数。
对于每组数据：
第一行，两个整数 $$$n,m(1\le m\le n\le 800)$$$，分别代表数组 $$$a$$$ 的长度和数组 $$$b$$$ 的长度。
第二行，$$$n$$$ 个整数 $$$a_1,\dots,a_n(1\le a_i\le n)$$$，代表数组 $$$a$$$。
第三行，$$$n$$$ 个整数 $$$x_1,\dots,x_n(1\le x_i\le 10^9)$$$，代表数组 $$$x$$$。
第四行，$$$n$$$ 个整数 $$$y_1,\dots,y_n(0\le y_i\le 10^9)$$$，代表数组 $$$y$$$。
第五行，$$$n$$$ 个整数 $$$z_1,\dots,z_n(0\le z_i\le 10^9)$$$，代表数组 $$$z$$$。
保证同一测试点内 $$$n$$$ 的总和不超过 $$$800$$$。
对于每组数据，输出一个整数 $$$score$$$，代表在最优替换方案下你的得分的最大值。
14 2 2 1 2 1 1 0 0 0 0 5 2 1 2 2 2 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 6 2 1 2 3 4 5 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 10 3 1 2 3 2 1 4 1 2 4 3 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 5 1 6 1 5 5 9 7 7 8 8 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 2 3 7 1 6 3 10 4 3 1 2 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 1 1 2 1 2 1 2 1 2 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2 1 2 9 9 1 2 8 1 5 2 1 2 2 2 1 8 2 4 5 9 6 8 3 1 8 5 5 3 2 6 6 2 1 2 3 4 5 1 3 2 8 4 9 5 3 0 2 1 9 8 1 2 9 0 8 3 10 3 1 2 3 2 1 4 1 2 4 3 5 9 8 1 5 7 9 8 7 1 5 5 6 1 2 8 7 2 1 0 9 0 0 0 2 7 9 6 9 6 10 5 1 6 1 5 5 9 7 7 8 8 10 14 14 16 8 7 17 2 6 5 6 1 7 9 9 0 5 9 0 2 4 4 6 5 6 4 3 8 0 8 10 2 3 7 1 6 3 10 4 3 1 2 9 2 1 4 3 6 7 1 1 8 0 0 0 0 0 0 0 0 0 0 3 7 4 2 2 0 1 4 7 3 10 1 1 2 1 2 1 2 1 2 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0
0 3 1 5 4 3 5 -3 -6 -11 -10 -4 1 3
公元 2225 年，为满足广大同学的精神需求，车南大学资产管理处投资 5000 万元，拟将车南大学广寒宫校区的猫猫升级为猫娘。
车南大学广寒宫校区可以视为一个 $$$n$$$ 行 $$$m$$$ 列的二维网格，每个格子有两种状态：有猫（Y）和无猫（N）。
显然，猫娘必须在有猫地区部署；并且，由于猫娘需要更加良好的饲养环境，任意两只猫娘不能相邻。定义相邻为上下左右四个格子相邻。
同学们希望猫娘的数量尽可能多，请你计算出猫娘的最大数量。
第一行两个整数 $$$n,m(1 \le n, m \le 8)$$$，表示网格大小。
接下来 $$$n$$$ 行，每行一个长度为 $$$m$$$ 的字符串，表示网格。
输出一个整数，表示猫娘的最大数量。
4 4 YYYY YYNN NYNY YYYY
7
在 $$$(1, 2), (1, 4), (2, 1), (3, 2), (3, 4), (4, 1), (4, 3)$$$ 位置部署猫娘可以最大部署 $$$7$$$ 只猫娘。
这道题是为了给坐牢的同学一点事情做，但是也不是很难，如果后面的算法题不会，可以试试这个。
你需要写一个 OCR 程序，能够正确识别有噪声的 01 字符串。
第一行两个整数 $$$n,m(1\le n\le 100, 1\le m \le 1000)$$$，表示矩阵的行数和列数。
接下来 $$$n$$$ 行，每行一个 01 字符串，表示输入的矩阵，1 表示白色像素，0 表示黑色像素。
具体见下发文件中的图片。
一行一个 01 串，表示识别结果。
样例见下发文件。
数据生成器统一运行生成了 20 个数据点，随机选取了 10 个作为下发的样例数据，实际测试数据包含全部 20 个数据点。
下发数据同时包含可视化的图片，供人工阅读调试。
样例输入： 
样例输出：
11001101111101
- 原始数据生成：选取一个随机 01 字符串（不含空格），使用同一字体，生成一张无噪声黑白图片。
- 噪声生成：给定噪声率 $$$p$$$，对于每个像素点，随机以概率 $$$p$$$ 翻转黑白状态，得到一张带噪声黑白图片。
- 输入生成：对于带噪声黑白图片，选取图片真实高度作为 $$$n$$$，选取图片真实宽度作为 $$$m$$$，将图片转换为 01 字符串，黑色像素为 0，白色像素为 1，得到输入数据。
- 输出生成：输出直接为最初选定的随机 01 字符串，标程不参与输出的生成。
- 全部 20 个测试点中，保证均满足 $$$64\le n\le 66$$$，$$$100 \le m \le 1000$$$ 且 $$$p=0.05$$$。