# 菜就多练
## A. 土拨鼠比沙雕
# Background
n只沙雕又愚蠢的土拨鼠，他们要比谁最沙雕
# Description
给出n只土拨鼠的沙雕程度，输出最沙雕的土拨鼠的编号
# Format
## Input
第一行一个整数，n
后面n行，每行一个整数，表示第i个土拨鼠的沙雕程度。
## Output
一个整数，表示最沙雕土拨鼠的编号，沙雕土拨鼠们的沙雕程度互不相同。
# Samples
```input1
5
78
87
98
35
10
```
```output1
3
```
# Limitation
n<=1000
每只土拨鼠最多能有多沙雕呢？答：最沙雕的土拨鼠的沙雕程度大于long long long的范围，但也不会超过10^1000次方，输入的数字没有前导零
---
## B. 土拨鼠跑酷
# Background
众所周知，土拨鼠跑酷是一款很有意思的游戏
# Description
数轴就是游戏的赛道，0我们不管他，1就是起点，后面的数，质数就是岩浆，合数就是陆地。在n的地方藏有宝藏，就算n是质数，那n也是陆地。土拨鼠桐桐想找到宝藏，他可以在陆地上走，记为walk(走过方块的个数)，他还可以可以跳过1～2个岩浆，记为jump(跳过岩浆的个数)，如果跳不过去，他就会用飞行器飞过去，记为fly(飞过岩浆的个数)。请你规划桐桐找到宝藏的路径。
# Format
## Input
一个数，n，表示宝藏在n
## Output
若干行，找到宝藏的路径。
# Samples
```input1
13
```
```output1
jump(2)
jump(1)
jump(1)
walk(2)
jump(1)
walk(1)
```
# Limitation
$n \le 2*10^6$
站在陆地上，跳到陆地上。站在陆地上，飞到陆地上。
如果无需走，就不必要走。
# 注意
文件重定向, run.in, run.out。8.31增加一组hack
---
## C. 土拨鼠的CSP-J初赛
# 故事背景
今天（9月18日）上午，CSP-J的初赛已经结束。同学们在“战场”上展现出了自己的实力。
其中，一道单项选择题难(jian)倒(dan)了(dao)一(wu)片(fa)同(miao)学(shu)：
```
14.一个字符串中任意个连续的字符组成的子序列称为该字符串的子串，则字符串 abcab 有（ ）个内容互不相同的子串。
A. 12
B. 13
C. 14
D. 15
```
这道题正确答案是B。它一共有
{a}、{b}、{c}、{ab}、{bc}、{ca}、{abc}、{bca}、{cab}、{abca}、{dcab}、{abcab}
这些字串。可**空串**却有些同学没考虑到。因此它一共有12 + 1 = 13个字串。
# 题目描述
今天上午去考试的土拨鼠做错了这道题，他想再自己出几道题目给自己练习一下。但土拨鼠不知道自己出的题目的正确答案，就无法判断自己有没有做对。现在请你将土拨鼠自己出的题编程计算出答案。
# 格式
## 输入
第一行一个整数 $t (1 \leq t \leq 100)$，表示一共有 $t$ 组测试样例。
接下来 $t$ 行，每行一个长度不超过200的字符串。字符串仅有小写字母组成。
## 输出
$t$ 行。每行一个整数 $a_i$，表示第 $i$ 个字符串的字串有多少个
# 样例
```input1
6
ajrajg
abcab
olympic
ccf
acjudge
csps
```
```output1
19
13
29
6
29
10
```
# 提示
别忘空串！！
---
## D. 土拨鼠打乒乓球
# 故事背景
今年是土拨鼠历2022年
$r$ 年在 $M$ 国举行的奥运会马上就要到了，而土拨鼠就是中国乒乓球队的一员，马上也要去 $M$ 国参加奥运会了！
可是土拨鼠第一次参加奥运会，心中总存在着忧虑。这时，土拨鼠和它的教练请你通过现在已经知道的数据，帮土拨鼠预测一下奥运赛场上土拨鼠的成绩，同时土拨鼠也需要加紧训练。
由于打乒乓球是两个人对打，因此“知己知彼 百战不殆”。现在勤劳的土拨鼠和他的教练通过观察其他各国乒乓球运动员的以往比赛，知道了它们的水平，也知道了它们的进步速度，请你帮助土拨鼠预测一下赛场上土拨鼠能赢几位选手。
# 题目描述
给定奥运赛赛场上土拨鼠面临的对手数量 $n$，和这些对手现在的水平 $a_i$ 以及进步速度 $b_i$（进步速度指的是从现在2022年到 $r$ 年之间的这几年中，平均每年的进步）。再给出土拨鼠自己现在的水平和进步速度。请你帮助土拨鼠预测一下赛场上土拨鼠一定能赢几位选手。(如果两只土拨鼠战斗力相同, 则不能一定战胜对手)
# 输入格式
第一行包含两个整数 $n(1\leq n\leq 32767)$ 和 $r(2023\leq r\leq32767)$ ，表示奥运会上土拨鼠的对手数量和奥运会的年份。
第二行包含两个整数 $x(1\leq x\leq 32767)$ 和 $y(1\leq y\leq 32767)$，表示土拨鼠现在的水平和土拨鼠的进步速度。
接下来 $n$ 行，每行包含一个字符串 $s_i$ 和两个整数 $a_i(1\leq a_i\leq 32767)$ 和 $b_i(1\leq b_i\leq 32767)$，分别表示每名对手的名字，以及它们现在的水平和进步速度。
# 输出格式
按字典序输出你预测的土拨鼠能赢得选手的名字（以空格分开，每5个名字换一行），并在最后一行输出赢的选手的数量。如果土拨鼠输给了所有对手，则只输出一行-1。
# 样例
```input1
7 2024
10 2
Sam 9 2
Peter 11 1
David 10 3
Marco 3 5
Billy 6 1
Ana 5 2
Tom 1 1
```
```output1
Ana Billy Marco Peter Sam
Tom
6
```
# 提示
注意每行包含5个名字
---
## E. 商场导购
# Description
作为H国知名商人，你在D城的市中心开了一家高人气商场，商场提供极其贴心的五星级导购服务。需要导购服务的顾客可以提前一天预约使用的时间段。目前有$N$位顾客预约了第二天导购服务，其中第i位顾客预约的时间段为$A_i$到$B_i$，注意导购服务包括了$A_i$和$B_i$两个时间段。很明显一位导购在同一个时间段只能服务一位客户。为了节约人工成本，你希望使用最少的导购满足全部顾客的要求。请你帮他求出第二天最少需要多少位导购。
# Format
## Input
输入有两行，第一行为两个正整数，表示预约导购服务的顾客数量。第2到$N$+1行，每行两个整数$A_i$，$B_i$，表示第i位顾客预约的时间段。
## Output
$输出一个整数，表示最少需要多少导购，可以满足全部顾客。$
# Samples
```input1
5
1 10
2 5
5 8
3 6
6 10
```
```output1
4
```
```input2
10
24 29
11 14
5 10
26 32
4 6
27 31
39 39
39 44
18 21
18 18
```
```output2
3
```
【样例1说明】
由于导购服务包括边界的时间段，所以[2, 5]和[5, 8]必须让不同的导购负责，那么只有[2, 5]和[6, 10]可以请同一个导购，其他都需要单独请导购。
# Limitation
对于30%的数据：1≤N≤10；
对于60%的数据：1≤N≤100，1≤Ai≤Bi≤100；
对于100%的数据：1≤N≤10000，1≤Ai≤Bi≤5000。
---
## F. 土拨鼠猜想
# 故事背景
在中国，一位土拨鼠有一个这样的猜想：任何一个大于2的偶数都可以分成两个偶数相加的形式。后来被证明。这就是著名的土拨鼠猜想。请你写一个程序，来验证这个猜想。
# 题目描述
给定一个整数 $n$，计算出 4 到 $n$ 之间每个偶数的土拨鼠猜想的所有解的个数，并分行输出。
# 输入
一个整数 $n$（$n$ 为大于2且小于等于1000000的整数）
# 输出
4 到 $n$ 之间每个偶数的土拨鼠猜想的所有解的个数（看不懂看提示），并分行输出。输出格式如下（仅为样例）：
如果 $n$ 为12，则输出：
4:1
6:1
8:2
10:2
12:3
### 输出时需注意：
* 一数一行
* 两数之间用英文的 : 隔开
# 样例
```input1
18
```
```output1
4:1
6:1
8:2
10:2
12:3
14:3
16:4
18:4
```
```input2
4
```
```output2
4:1
```
# 提示
假设 $n$ 为12：
```
4:1
6:1
8:2
10:2
12:3
```
4分成两个偶数相加的形式为：2+2，故为1
6分成两个偶数相加的形式为：2+4，故为1
8分成两个偶数相加的形式为：2+6 和 4+4，故为2
10分成两个偶数相加的形式为：2+8 和 4+6，故为2
12分成两个偶数相加的形式为：2+10 和 4+8 和 6+6，故为3
---
## G. 麦森数（超级难！！）
# 题目背景
形如 $2^p$-1 的素数称为麦森数，这时 P 一定也是个素数。但反过来不一定，也就是如果 P 为素数， $2^p$ -1 不一定也是素数。到 1998 年底，人们已找到了 37 个麦森数。最大的一个是 P=3021377，它有 909526 位。麦森数有许多重要应用，它与完全数密切相关。
*PS：这和题目没什么太大关系 ^ _ ^*
### 重要说明：此题为转载题目，来源在最后
# 题目要求
输入一个正整数 P ， 输出 $2^p$ - 1的位数，并在下一行输出它的后500位数字，不够的补0。
## 输入
输入 P ， $1000\leq P\leq 310000$ .
## 输出
两行，第一行是 $2^p-1$ 的位数， 第二行是$2^p-1$的后500位（不够补0）
# 样例
```input1
1279
```
```output1
386
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010407932194664399081925240327364085538615262247266704805319112350403608059673360298012239441732324184842421613954281007791383566248323464908139906605677320762924129509389220345773183349661583550472959420547689811211693677147548478866962501384438260291732348885311160828538416585028255604666224831890918801847068222203140521026698435488732958028878050869736186900714720710555703168729087
```
# 时限
一秒钟，125MB
## 来源
洛谷题库 | 计算机教育
---
## H. 土拨鼠的约分
# 题目描述
给定一个分数，帮助土拨鼠将它约分到最简分数。
# 输入
一个字符串。字符串由 分子/分母 的形式表示，而且其中的 '/' 号个数不限，也就是说输入`5/2`或`5/////////2`都表示的是$\frac{5}{2}$这个分数。分子分母均在long long范围内的正整数（不包括0）。
# 输出
输出3行，为约分后的分数。
第一行为分子；
第二行为分数线 ------- （减号的个数由分子与分母中位数最多的个数所决定）；
第三行为分母；
重要提示：如果最后约出分母为1的情况，则输出一行，为一个整数。
# 样例
```input1
3//////6
```
```output1
1
-
2
```
```input2
30////////////////////4
```
```output2
15
--
2
```
```input3
1/1
```
```output3
1
```
# 提示
输入字符串中 '/' 号的个数不大于80个。
---
## I. A + B 绝杀版
# Watermelon
## 题意翻译
判断输入的正整数能否分成两个正偶数，能则输出`YES`，不能则输出`NO`。
## 题目描述
One hot summer day Pete and his friend Billy decided to buy a watermelon. They chose the biggest and the ripest one, in their opinion. After that the watermelon was weighed, and the scales showed $ w $ kilos. They rushed home, dying of thirst, and decided to divide the berry, however they faced a hard problem.
Pete and Billy are great fans of even numbers, that's why they want to divide the watermelon in such a way that each of the two parts weighs even number of kilos, at the same time it is not obligatory that the parts are equal. The boys are extremely tired and want to start their meal as soon as possible, that's why you should help them and find out, if they can divide the watermelon in the way they want. For sure, each of them should get a part of positive weight.
## 输入输出格式
#### 输入格式
The first (and the only) input line contains integer number $ w $ ( $ 1<=w<=100 $ ) — the weight of the watermelon bought by the boys.
#### 输出格式
Print YES, if the boys can divide the watermelon into two parts, each of them weighing even number of kilos; and NO in the opposite case.
## 输入输出样例
#### 输入样例 #1
```
8
```
#### 输出样例 #1
```
YES
```
## 说明
For example, the boys can divide the watermelon into two parts of 2 and 6 kilos respectively (another variant — two parts of 4 and 4 kilos).
[洛谷链接](https://www.luogu.com.cn/problem/CF4A)
---
## J. 【例13.2】 电子表
说明
电子表上的时间显示方法形如xx:xx:xx，现在给出一个时间，单位是秒，要求按照电子表格式输出，输出保证不会超过 $24$ 小时。
输入格式
输入一个时间。
输出格式
把时间转化成电子表格式输出。
样例
3701
01:01:41
---
## K. 土拨鼠爬井
# 故事背景
一天，土拨鼠正在路上悠闲的看着一本书。书中有一篇井底之蛙的故事，土拨鼠看完后，想到了今天上数学课时老师讲的“青蛙爬井问题”。正在这时，土拨鼠没看路，掉进了一个深井里。这就变成了“土拨鼠爬井问题”。请你编程计算一下，可怜的土拨鼠要多少天才能爬上来。
# 题目描述
现在知道了井深 $h$ 米，土拨鼠白天向上爬 $n$ 米，但是晚上会掉下来 $m$ 米。请你编程计算一下，可怜的土拨鼠要多少天才能爬上来。
# 输入
三个正数 $h$ 和 $n$ 和 $m$（1< m < n $\leq$ h $\leq$ 100），分别表示井深 $h$ 米，白天爬向上 $n$ 米，和晚上下落 $m$ 米。
# 输出
输出土拨鼠需要多少天才能爬上地面。
# 样例
```input1
10 5 2
```
```output1
3
```
# 提示
样例解释：
井深10米，白天爬5米，晚上降2米：
第一天：白天高5米，晚上高3米。
第二天：白天高8米，晚上高6米。
第三天：白天高11米。
故为3。
---
## L. 练7.1 埃及金字塔
说明
金字塔的侧面是由四个大小相同的等腰三角形构成的。给出三角形的底和高，输出其中一个侧面的面积。
输入格式
输入两个数分别是底和高。
输出格式
输出三角形的面积。
样例
9 10
s=45
---
## M. 蜜汁
# Background
小 $Q$ 是一个劳逸结合的孩子（☞学习两分钟，游戏两小时）
# Description
小 $Q$ 玩到了一个游戏，大概是这样的：
> 有一个迷宫，迷宫四处全是危险，但值得庆幸的是这个迷宫的路是一些圆，可以走，要从一个坐标走到目标点。
小 $Q$ 并不会，所以他来请教你，你只需要判断这个是否有解就可以啦。
原始有一个在 $(0,0)$ 点半径为 $1$ 的圆。
$\color{white}{\texttt{有解输出1，无解输出0}}$
# Format
## Input
第一行一个整数 $T$ 表示有 $T$ 关。
接下来第一行两个数字 $x_e, y_e$ 表示终止点。
然后就是一个整数 $n$。
然后 $n$ 行，三个数，代表圆的中心的坐标，以及半径长度。
## Output
$T$ 行，每行一个数，表示答案。
# Limitation
$1 \le T \le 10$
$-10^8 \le x, y,x_e,y_e\leq10^8$
$1 \le r\le 10^8$
$1\le n \le 1000$
---
## N. 瓜子
# Background
小 $Q$ 买了 $n$ 粒瓜子。
# Description
小 $Q$ 每次都会从这堆瓜子中挑出一粒，他每次吃完一粒瓜子后，就会得到两瓣瓜子壳，他会把瓜子壳也丢进瓜子堆里面去。
如果他拿到了自己之前吃瓜子留下的瓜子壳，他就会把拿到的瓜子壳丢掉，否则就吃掉拿到的瓜子并且把瓜子壳丢进去。
现在设每次小 $Q$ 拿到每一粒瓜子或者是瓜子壳的概率是均等的，问 小L 期望多少次能够把瓜子拿完。
# Format
## Input
一行一个正整数 $n$。
## Output
一行一个整数表示结果对于 `998244353` 取模的结果。
# Samples
```input1
2
```
```output1
3
```
# Limitation
$n=2$ 的时候，这个时候 小L 第一次拿到的肯定是瓜子，然后现在瓜子堆里面有 $1$ 粒瓜子，$2$ 个瓜子壳。接下来他有 $\frac13$ 的概率拿到瓜子，有 $\frac23×\frac13$ 的概率第一次拿到瓜子壳，第二次拿到瓜子。还有 $\frac23×\frac12=\frac13$ 的概率再拿两次都拿到瓜子壳，最后拿到瓜子。
所以期望的次数：$2×\frac13+3×\frac13+4×\frac13=3$
对于 $100\%$ 的数据满足 $n≤2×10^3$。
---
## O. 土拨鼠玩灯
# Background
土拨鼠蔚蔚捡到了一盏奇怪的灯
# Description
这盏灯会有规律的闪烁, 灯泡每次闪烁后的颜色可以用 $n$ 个二元组 $(a_1,b_1),(a_2,b_2),\cdots,(a_n,b_n)$ 来表示。机器会对每个 $i=1,2,3,\cdots,n$闪烁 $a_i$次，并且这 $a_i$次闪烁发出的颜色都为 $b_i$。
现在蔚蔚想知道，机器第 $m$ 次闪烁后，发出的颜色是什么。
# Format
## Input
第一行两个正整数 $n,m$。
第二行 $n$ 个正整数 $a_1,\cdots,a_n$。
第三行 $n$个正整数 $b_1,\cdots,b_n$。
## Output
输出一行一个正整数表示答案。
# Samples
## 样例1
```input1
4 5
1 2 3 4
4 3 2 1
```
```output1
2
```
#### 样例解释1
机器一共闪烁了 $10$ 次。每次闪烁后颜色分别为：$4,3,3,2,2,2,1,1,1,1$。
第 $5$ 次闪烁后，机器的颜色为 $2$。
## 样例2
```input2
4 3
1 1 1 1
1 2 3 4
```
```output2
3
```
#### 样例解释2
机器一共闪烁了 $4$ 次。每次闪烁后颜色分别为：$1,2,3,4$。
第 $3$ 次闪烁后，机器的颜色为 $3$。
# Limitation
对于 $100\%$ 的数据，$1\le n\le 10^5,1\le m,a_i,b_i\le 10^9,m\le \sum a_i$。
# 注意
输出时每行末尾的多余空格，不影响答案正确性
要求使用「文件输入输出」的方式解题，输入文件为 city.in，输出文件为 city.out
---
## P. 土拨鼠一家总共有几个南桐
# Background
Special for beginners, ^_^
# Description
Given two integers x and y, print the sum.
# Format
## Input
Two integers x and y, satisfying $0\leq x,y\leq 32767$ .
## Output
One integer, the sum of x and y.
# Samples
```input1
123 500
```
```output1
623
```
# Limitation
1s, 1024KiB for each test case.
---
## Q. 土拨鼠判断某年某月的天数(我不知道怎么写评测设置)
## 题目描述
小镇里有 $n$ 个地点，通过 $n-1$ 条道路连通，每条道路长 $1$ 。两个被某条道路直接相连的地点被称为相邻地点。也就是说，所有地点构成一棵包含 $n$ 个节点的树。
小镇要筹办 $q$ 场奇迹之夜的活动。每个地点具有正整数的日常人气 $m_i$ 和聚会人气 $w_i$ 。另外，小镇里有一个车站位于点 $k$ ，车站的交通范围为 $L$ 。
活动时，每个地点（包括车站在内）需要选择三项之一：
举办日常活动：该地点活动的人气为它的日常人气 $m_i$ 。
举办聚会活动：该地点活动的人气为它的聚会人气 $w_i$ 。要举办聚会，要么它至少有一个相邻地点成为后勤基地，要么它离车站即 $k$ 号地点的距离（两点之间的最小道路数）不超过交通范围 $L$ 。
成为后勤基地：人气为零，但是相邻地点可以举办聚会。
一场活动中小镇的总人气为所有地点的人气之和。
每场活动中车站的交通范围 $L$ 可能不同，其余信息都相同。你需要求出每次活动最大可能的小镇总人气。
## 输入格式
请注意这道题需要使用文件输入输出，例如 freopen。文件名见题目标题下方的评测信息。
第一行两个整数 $n, q$ ，表示地点个数和活动场数；
第二行 $n$ 个整数，其中第 $i$ 个表示 $i$ 号地点的日常人气 $m_i$ ；
第三行 $n$ 个整数，其中第 $i$ 个表示 $i$ 号地点的聚会人气 $w_i$ ；
第四行一个整数 $k$ ，表示车站所在的地点。
接下来 $n-1$ 行，每行两个整数 $u,v$ ，表示有一条道路连接 $u,v$ 。保证任意两地点可以通过道路直接或间接连通。
接下来 $q$ 行，其中第 $i$ 行包含一个整数 $L_i$ ，表示第 $i$ 次活动中车站的交通范围 $L_i$ 。
## 输出格式
请注意这道题需要使用文件输入输出，例如 freopen。文件名见题目标题下方的评测信息。
输出共 $q$ 行，其中第 $i$ 行一个整数，表示第 $i$ 次活动最大可能的小镇总人气。
## 样例
样例输入 1
```
6 3
9 8 1 8 9 5
6 6 9 10 1 7
1
2 1
3 2
4 1
5 4
6 5
1
2
3
```
样例输出 1
```
42
50
52
```
样例 2、3、4
见。
## 数据范围与提示
对于 $100\%$ 的数据， $1 \leq n, q \leq 10^5,0\le L_i\le 10^5,1 \leq m_i, w_i \leq 10^9$
一共有 $20$ 个测试点。部分测试点满足的性质如下：
$1,2$ 号： $w_i=1$ ；
$3,4$ 号： $q=1, L_1=n$ ；
$1,2,3,4,5,6$ 号： $1\leq n,q \leq 10$ ；
$1,2,3,4,5,6,7,8,9,10,11,12,13,14$ 号： $1 \leq n, q\leq 5000$ ；
---
## R. 东京吃货
# 背景
金木研想要成为赫者，他到底要吃多少只喰种，让我们帮他算一算吧！！！！！
# 描述
现在有两种喰种共50只，一种是有两个赫包的（h2），一种是有四个赫包的（h4），共有赫包160个。求h2 h4各多少只？
# 输出
先输出h2的再输出h4的，用空格隔开
---
## S. P4911 河童重工的计算机
# 河童重工的计算机
## 题目背景
河童重工业会社的计算机产品在幻想乡中有着极其广泛的应用。
有一天，妖怪之山发大水啦！洪水夹杂着泥沙和滚木汹涌着冲进了河童的城市。
本来河童们的机械设施都是防水的，可是洪水还是对城市造成了不小的破坏。其中，河童们的服务器被砸坏了！
坏掉的电脑在短时间内不能修复，可是幻想乡里的许多事情都离不开河童们的服务器！河童们也很无奈，于是荷取找到了你！你作为一名优秀的信竞选手，决定帮助荷取，减轻服务器故障所带来的压力。
## 题目描述
你从荷取那里得到了一份纸质资料，扫描版在这里：
[Ktx-65式微处理器汇编语言规范文件.pdf](https://www.touhou-oi.tk/uploads/Ktx-65%E5%BC%8F%E5%BE%AE%E5%A4%84%E7%90%86%E5%99%A8%E6%B1%87%E7%BC%96%E8%AF%AD%E8%A8%80%E8%A7%84%E8%8C%83%E6%96%87%E4%BB%B6.pdf)
（若此网站无法打开，请在附件中下载）
（为什么说是扫描版呢，因为，你应该不能复制里面的文字）
以下这一段是汇编教程附带的示例：
```asm
[ progfunc.asm ]
[ Shows the function functionailties of the KTX-65 ALI ]
[main]
wint #line; [output the current physical line number]
wch 13; [putchar \r]
wch 10; [putchar \n]
callfunc $Function1;
callfunc $Function2;
hlt; [halt]
function $Function1;
rint %r1; [read int]
add %r2 1 %r2; [loop contents]
lle %r2 %r1; [loop conditions]
jif 2; [end loop conditional jump]
wint %r2; [output int]
wch 13; [putchar \r]
wch 10; [putchar \n]
ret; [return]
function $Function2;
rint %r1; [read int]
rint %r2; [read int]
add %r1, %r2; [add]
wint %val; [output value]
wch 13; [putchar \r]
wch 10; [putchar \n]
ret; [return]
```
你需要用洛谷评测机支持的语言编写一个程序，它读入一个Ktx-65汇编语言程序和一段输入，解释运行这个程序，然后输出这个程序输出的东西。
## 输入格式
第一行是一个整数N，表示汇编程序的行数。
接下来N行是这个汇编程序，保证不会出现空行。
接下来的所有行都是这个汇编程序的输入。
## 输出格式
一堆东西，表示这个汇编程序的输出。
评测系统将以逐字节比较的方式判断你的输出是否正确。~~假的，洛谷不支持
## 样例 #1
### 样例输入 #1
```
5
rint %r1;
rint %r2;
add %r1 %r2;
wint;
hlt;
5 4
```
### 样例输出 #1
```
9
```
## 提示
**注意：**样例输出中只有9这一个字节。
对于10%的数据：程序中只有输入和输出的指令，且不会出现数字常量，也不会有注释。
对于另外10%：程序中只有输入、输出和加法指令，且没有注释。
对于另外30%：包括除函数调用和跳转在内的所有指令。
对于剩下50%：指令没有限制。
对于全部的数据：命令条数不超过50000条，剩余输入不超过500千字节，程序需要执行的步数不超过80000步。
保证汇编程序和数据不出现编译或是运行时错误。
保证程序输入足够满足汇编程序中读入的需要。
保证`kunkka`不会做。
保证`kunkka`看了本题后会说`我靠！`。
不保证这是或不是一道毒瘤题
不保证考试时会不会有人AC这道题
不保证有这道题的考试会不会有人AK
不保证出题人为：tanzicheng
考试时打不开河童给的文件可以向我索要，不保证是否会回答
~~其实这道题数据非常水，只是量大而已~~
## 附件下载
[Ktx-65式微处理器汇编语言规范文件.pdf](https://www.luogu.com.cn/fe/api/problem/downloadAttachment/byhp459q) 635.56KB
---
## T. 土拨鼠进监狱
# Background
土拨鼠进监狱了，他需要写出n的全排列才能出狱。
# Description
给出n，输出n的全排列。
# Format
## Input
一行，一个数n
## Output
$n!$行，每行是n的一个全排列，按字典序输出。
# Samples
```input1
3
```
```output1
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
```
# Limitation
1秒，256mb。$n<=8$
---
## U. 土拨鼠和猴子
# 土拨鼠和猴子打架
一只土拨鼠和n只喜欢吃shi味干脆面的猴子打架 土拨鼠输了 伤心的回家找妈妈
# 题目
猴子因为经常吃 shi味干脆面 所以他进化了 两只土拨鼠妈妈可以在一个小时内打败一只猴子 而猴子因为喜欢乱喷shi 每隔半个小时就会变得虚弱 如果超过一个小时吃不shi味干脆面 就会缩水 变成一只狗 丧失战斗能力
## 输入
输入猴子数量
# 输出
输出最少需要多少土拨鼠妈妈
```
---
## V. 土拨鼠解密码
# Background
土拨鼠被困在了密室里，她想要出去。墙上有一个密码锁，只要打出所有数字就可以了。但按键只剩下$+5$键，$+7$键与$\sqrt \ $键，只要用这三个键从$0$开始一直打倒出现所有密码就行了。（不能大于100，不能出现非整数，不能重复）
举例：要打出$2$来：
$0\to5\to12\to17\to24\to29\to36\to6\to11\to16\to4\to2$，就能得到$2$。
你要输出的就是这种格式。
# Description
给出1个数$a$，给出一条能够按题目要求得到这个数的路径，如果不行输出"Tuboshu will die in here".
# Format
## Input
1个$a$，表示要得到的密码。
如果有多个解，请输出字典序最小的。
比如 $12393$ 和 $12344$要输出$12393$，因为第五项$3$更小。必须按顺序打出。
## Output
一个字符链，表示得到密码的过程，具体格式为：
a to b to c to d to e
注意，每得到一个密码，需要紧跟着输出一个“Yell。（如果得不到密码，请输出："Tuboshu will die in here".）。
# Samples
```input1
2
```
```output1
0 to 5 to 12 to 17 to 24 to 29 to 36 to 6 to 11 to 16 to 4 to 2Yell
```
# Limitation
$$
1\le a_i\le100
$$
---
## W. [IOI2023] 封锁时刻
# [IOI2023] 封锁时刻
## 题目背景
这是一道交互题，你只需要实现代码中要求的函数。
你的代码不需要引用任何额外的头文件，也不需要实现 `main` 函数。
本题仅支持 C++ 语言提交。
## 题目描述
匈牙利有 $N$ 个城市，编号依次为 $0$ 到 $N - 1$。
这些城市之间由 $N - 1$ 条双向道路连接，编号为 $0$ 至 $N - 2$。对每个 $j$（$0 \le j \le N - 2$），第 $j$ 条道路连接城市 $U[j]$ 和城市 $V[j]$，其长度为 $W[j]$，表示这两个城市之间的交通时间为 $W[j]$ 个时间单位。每条道路连接两个不同的城市，且每两个城市之间最多由一条道路连接。
两个不同城市 $a$ 和 $b$ 之间的一条**路径**是一个由不同城市组成的序列 $p_0, p_1, \ldots, p_t$，满足以下条件：
* $p_0 = a$，
* $p_t = b$，
* 对每个 $i$（$0 \le i \lt t$），存在一条道路连接 $p_i$ 和 $p_{i + 1}$。
利用这些道路从任意一个城市到任意一个其他的城市都是有可能的。换言之，任意两个不同城市之间都存在路径。
可以证明两个不同城市之间的路径是唯一的。
一条路径 $p_0, p_1, \ldots, p_t$ 的**长度**是这条路径上连接相邻城市的 $t$ 条道路的长度之和。
在匈牙利，很多人都会在建国日去参加在两个主要城市举行的庆祝活动。当庆祝活动结束时，他们会回家。政府为了防止人群干扰当地人，所以决定在特定时刻封锁城市。每个城市被政府分配一个非负的**封锁时刻**。政府决定所有城市的封锁时刻总和不得超过 $K$。具体来说，对每个 $i$（$0 \leq i \leq N - 1$），分配给城市 $i$ 的封锁时刻是一个非负整数 $c[i]$。所有 $c[i]$ 之和不超过 $K$。
考虑一个城市 $a$ 和某个封锁时刻的分配方案，我们说城市 $b$ 是从城市 $a$ 可达的当且仅当以下两种情况中的任意一种情况成立。
情况 1：$b = a$。
情况 2：这两个城市之间的路径 $p_0, \ldots, p_t$ （$p_0 = a$ 且 $p_t = b$）满足以下条件：
* 路径 $p_0, p_1$ 的长度最多为 $c[p_1]$，并且
* 路径 $p_0, p_1, p_2$ 的长度最多为 $c[p_2]$，并且
* $\ldots$
* 路径 $p_0, p_1, p_2, \ldots, p_t$ 的长度最长为 $c[p_t]$。
今年，两个主要的庆祝地点位于城市 $X$ 和 $Y$。
对于每一个封锁时刻的分配方案，可以定义一个**便利分数**，其定义为下面两个数字之和：
- 从城市 $X$ 可达的城市个数。
- 从城市 $Y$ 可达的城市个数。
注意如果一个城市既能从城市 $X$ 可达也能从城市 $Y$ 可达，那么它在计算便利分数时计算两次。
你的任务是计算能被某个封锁时刻分配方案实现的最大便利分数。
## 输入格式
令 $C$ 表示场景数，即调用 `max_score` 的次数。
评测程序实例按以下格式读取输入：
* 第 $1$ 行：$C$
以下是 $C$ 个场景的描述。
评测程序实例按以下格式读取每个场景的描述：
* 第 $1$ 行：$N \; X \; Y \; K$
* 第 $2 + j$ 行（$0 \le j \le N - 2$）：$U[j] \; V[j] \; W[j]$
## 输出格式
评测程序实例按以下格式为每个场景打印单独一行
* 第 $1$ 行： `max_score` 的返回值
## 样例 #1
### 样例输入 #1
```
2
7 0 2 10
0 1 2
0 3 3
1 2 4
2 4 2
2 5 5
5 6 3
4 0 3 20
0 1 18
1 2 1
2 3 19
```
### 样例输出 #1
```
6
3
```
## 提示
#### 【实现细节】
你要实现以下函数。
```
int max_score(int N, int X, int Y, int64 K, int[] U, int[] V, int[] W)
```
* $N$：城市的个数
* $X$，$Y$：两个主要庆祝城市
* $K$：封锁时刻总和的上界
* $U$，$V$： 长度为 $N - 1$ 的描述道路连接情况的数组
* $W$：长度为 $N - 1$ 的描述道路长度的数组
* 该函数要返回能被某个封锁时刻分配方案实现的最大便利分数
* 每个测试用例可以多次调用该函数
#### 【例子】
考虑以下调用：
```
max_score(7, 0, 2, 10,
[0, 0, 1, 2, 2, 5], [1, 3, 2, 4, 5, 6], [2, 3, 4, 2, 5, 3])
```
这对应以下道路网络：
假设封锁时刻如下分配：
| **城市** | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ |
|:----------------:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|
| **封锁时刻** | $0$ | $4$ | $0$ | $3$ | $2$ | $0$ | $0$ |
注意所有封锁时刻之和为 $9$，不超过 $K = 10$。城市 $0$，$1$ 和 $3$ 都是从城市 $X$（$X = 0$）可达的，而城市 $1$，$2$ 和 $4$ 都可以从城市 $Y$（$Y = 2$）可达。 因此，便利分数为 $3+3 = 6$。不存在封锁时刻分配方案使得便利分数大于 $6$，所以该函数应该返回 $6$。
考虑另外一个调用：
```
max_score(4, 0, 3, 20, [0, 1, 2], [1, 2, 3], [18, 1, 19])
```
这对应以下道路网络：
假设封锁时间如下分配：
| **城市** | $0$ | $1$ | $2$ | $3$ |
|:----------------:|:---:|:---:|:---:|:---:|
| **封锁时刻** | $0$ | $1$ | $19$| $0$ |
城市 $0$ 从城市 $X$（$X = 0$）可达，而城市 $2$ 和 $3$ 都是可以从城市 $Y$（$Y=3$）可达的。因此，便利分数是 $1 + 2 = 3$。不存在封锁时刻分配方案使得便利分数大于 $3$，所以函数应该返回 $3$。
#### 【约束条件】
* $2 \le N \le 200\,000$
* $0 \le X \lt Y \lt N$
* $0 \le K \le 10^{18}$
* $0 \le U[j] \lt V[j] \lt N$ (对每个 $j$ 满足 $0 \le j \le N - 2$)
* $1 \le W[j] \le 10^6$ (对每个 $j$ 满足 $0 \le j \le N - 2$)
* 利用这些道路可以从任意一个城市走到任意另外一个城市。
* $S_N \le 200\,000$，其中 $S_N$ 是所有调用函数 `max_score` 的 $N$ 的总和。
#### 【子任务】
我们说一个道路网络是**线性的**如果道路 $i$ 连接城市 $i$ 和 $i+1$（对每个$0 \le i \le N - 2$ 的 $i$）。
1. （8 分）从城市 $X$ 到城市 $Y$ 的路径长度大于 $2K$。
1. （9 分）$S_N \le 50$，道路网络是线性的。
1. （12 分）$S_N \le 500$，道路网络是线性的。
1. （14 分）$S_N \le 3\,000$，道路网络是线性的。
1. （9 分）$S_N \le 20$
1. （11 分）$S_N \le 100$
1. （10 分）$S_N \le 500$
1. （10 分）$S_N \le 3\,000$
1. （17 分）无额外的约束条件。
---