Problem 1. note

Input file: note.in

Output file: note.out

Time limit: 1 second

最近有一款很火的游戏，叫做八分音符酱，它和马里奥很相似，不过它的跳跃距离是由你的声音大小来控制

的。不过我们现在对玩法就行一些修改：

现有一共有n 个柱子，两个相邻的柱子之间的初始水平距离为1，蠢蠢的jyb 现在在最矮的柱子上，他每次

只能向恰好比这个柱子高的另一个柱子跳跃，最后要跳到最高的柱子上。

jyb 需要从第二个柱子跳到第一个柱子，再跳到第三个柱子

jyb 的最大声音为d，代表他能在满足jposi ? posj j + jheighti ? heightj j d 的两个柱子之间跳跃。假设我

们可以在不改变它们位置的相对顺序的前提下水平移动柱子，调整他们的水平位置(但相邻间隔至少为1，且

为整数)。for example

 

 

jyb 想问你：在能从最矮柱子跳到最高柱子的前提下，它们(最矮柱子跳到最高柱子) 的最大水平距离是多少。

Input

第1 行，1 个整数T, 表示数据组数，对于每组数据：

第1 行，1 个整数n;m，表示一共有多少个柱子。

接下来1 行，有n 个数，hi 表示柱子的高度。保证柱子高度互不相同

Output

对于每组数据，输出在能从最矮柱子跳到最高柱子的前提下，它们的最大水平距离是多少。如果不能，输出-1

Sample

note.in 

2

3 4

3 2 4

3 4

3 2 6

note.out

2

-1

note.in 

2

5 10

4 2 1 8 10

5 2

10 8 2 1 4

note.out

12

-1

Note

• 对于30% 的数据，1 <= n <=100,1=<d<=1000,1<=hi<=1000;

• 对于100% 的数据，1<=T<=100，1<=n<= 1e3,1<=d <=1e6,1<=hi <=1e6。

Problem 2. number

Input file: number.in

Output file: number.out

Time limit: 1 second

一天，jyb 去视察他的军队。军队中的每名士兵都有一个编号，从1 开始编号，现在jyb 从抽出了一些编号

连续的士兵，想让它们排成1 列，排队的规则是这样的：对于第i 名士兵，他的编号必须是i 的倍数。现在

jyb 想知道是否能成功排队。

Input

第1 行，1 个整数T, 表示数据组数，对于每组数据：

第1 行，2 个整数n; s，n 表示选中的士兵数，编号是s + 1; s + 2; s + 3; ……; s + n

Output

对于每组数据，如果能成功排队，输出Yes；不能，输出No。

Sample

number.in

2

5 14

4 11

number.out

No

Yes

Note

• 对于10% 的数据，1<=n<=10,1<=s<=30;

• 对于30% 的数据, 1<=n<=10000,1<=s<=10000;

• 对于100% 的数据，1 <= T <=1000，1 <=n <=1e9,1 <=s <=1e9。

Problem 3. roadblock

Input file: roadblock

Output file: roadblock.out

Time limit: 1 second

震惊！cky 竟率兵攻打jyb！

jyb 面对强敌，振作精神，想要抗击侵略。jyb 的国家一共有n 个城市，m 条距离为1 的双向道路。现在jyb

的所在地是1 号城市，cky 已经占领了n 号城市。jyb 得到线报，cky 想要走最近的路线抓到自己，而jyb 还

在调集部队，所以他希望拖延一点时间。他派出了一些工程人员去破坏道路，破坏每条道路都要消耗一定的

资源，jyb 希望消耗最小的资源并且保证能拖延到cky。

Input

第1 行，1 个整数T, 表示数据组数，对于每组数据：

第1 行，2 个整数n;m，表示城市数和道路数

接下来m 行，每行3 个整数u; v;w, 表示城市u 到城市v 有一条路，破坏消耗的资源为w。

Output

对于每组数据，输出最小消耗的资源。

Sample

roadblock.in

1

4 4

1 2 1

2 4 2

3 1 3

4 3 4

roadblock.out

4

Note

• 对于30% 的数据,1<=n <=100，1<= m<= 1000

• 对于100% 的数据,1 <=T <= 5,1 <= n <=1000，1 <= m <= 10000，1 <= w <= 32767。

Problem 4. army

Input file: army.in

Output file: army.out

Time limit: 1 second

战争还在继续进行，jyb 还控制着n 个城市，n 个城市之间有着m 条双向道路，每条道路上都有一些数量的

驻军。根据战局，jyb 想派出军队去支援前线，但是为了防止cky 派出特种部队偷袭某些道路，使得自己的城

市之间交通被切断（不能互相到达），所以jyb 必须要在重要的道路上保留驻军。jyb 想知道自己最多能调遣

多少军队。

为了能尽量多的调遣军队，jyb 决定再修一些路，现在给出了修路的计划(由于正在打仗，现有的资源只能一

条路一条路地修，且按照计划)。jyb 还想知道，每有一条新路修成，jyb 能调遣多少军队。

Input

第1 行，3 个整数n; m; q，表示城市数量，道路数。城市用1; 2; : : : ; n 编号。

接下来m 行，每行3 个整数u; v;w，表示连接城市u; v 的道路上有w 数量的军队

接下来q 行，每行2 个整数u; v，表示新修一条连接城市u; v 的道路。保证u! = v，保证城市之间连通

Output

输出一共q + 1 行，每行输出能调遣的军队。

Sample

army.in

4 4

1 2 5

2 1 5

2 3 5

1 4 5

2

1 2

3 4

army.out

10

0

10

Note

• 对于30% 的数据，1 <=n<= 500，1 <=m <= 1000，1 <= q <=500；

• 对于100% 的数据，1 <=n <=100000，1 <= m <= 200000，1 <= q <=100000,1<= w <=1000

惨不忍睹！！！！