Mike有一个农场，这个农场$n$个牲畜围栏，现在他想在每个牲畜围栏中养一只动物，每只动物可以是牛或羊，并且每个牲畜围栏中的饲养条件都不同，其中第$i$个牲畜围栏中的动物长大后，每只牛可以卖$a[i]$元，每只羊可以卖$b[i]$元，为了防止牛羊之间相互影响，Mike找到了$m$条规律，每条规律给出一个三元组$(i,j,k)$表示如果第$i$个围栏和第$j$个围栏养的是不同的动物，那么Mike就需要花费$k$的代价请人帮忙处理牛羊之间的影响。不过同时Mike也发现$k$条特殊的规则$(S,a,b)$，表示如果$S$中所有牲畜围栏中都养的是动物$a$，那么Mike可以获得$b$的额外收入。现在Mike想知道他该在哪些围栏中饲养什么动物才能使得总收益最大，为了简化问题，你只需要输出最大收益。
神犇Aleph在SDOI Round2前立了一个flag：如果进了省队，就现场直播喝崂山白花蛇草水。凭借着神犇Aleph的实力，他轻松地进了山东省省队，现在便是他履行诺言的时候了。蒟蒻Bob特地为他准备了$999,999,999,999,999,999$瓶崂山白花蛇草水，想要灌神犇Aleph。神犇Aleph求（跪着的）蒟蒻Bob不要灌他，由于神犇Aleph是神犇，蒟蒻Bob最终答应了他的请求，但蒟蒻Bob决定将计就计，也让神犇Aleph回答一些问题。具体说来，蒟蒻Bob会在一个宽敞的广场上放置一些崂山白花蛇草水（可视为二维平面上的一些整点），然后询问神犇Aleph在矩形区域$(x_1,y_1),(x_2,y_2)(x_1\le x_2$且$y_1\le y_2$，包括边界$)$中，崂山白花蛇草水瓶数第$k$多的是多少。为了避免麻烦，蒟蒻Bob不会在同一个位置放置两次或两次以上的崂山白花蛇草水，但蒟蒻Bob想为难一下神犇Aleph，希望他能在每次询问时立刻回答出答案。神犇Aleph不屑于做这种问题，所以把这个问题交给了你。
话说有一天doyouloveme和vfleaking到山里玩。谁知doyouloveme刚刚进山，所有的鸟儿竟被他的神犇气场给惊得全部飞走了。vfleaking顿时膜拜不已。
这时鸟王用鸟语说道：“!@#%……?”安抚了一下众鸟的情绪。鸟王生性好斗，作出了一个决定——要排鸟布阵把刚才吓到它们的人类赶出山去。
每只鸟都有一个编号，都有一个威武值。每秒钟鸟王都会发一个命令，编号为$v$的鸟飞到$(x,y)$去（坐标系原点是山顶，坐标单位为鸟爪）。鸟飞得很快，一秒之内就飞到了，可以看作是瞬间移动。如果编号为$v$的鸟和编号为$u$的鸟某一时刻处在同一位置，它们就会互相鼓励，增加各自的士气值和团结值。一只鸟的士气值等于此刻与它处在同一位置的鸟中的威武值的最大值，团结值等于此刻与它处在同一位置的鸟的只数。如果每一时刻都没有鸟与它处在同一位置，则士气值和团结值都为$0$。要注意自己不能鼓励自己，计算士气值和团结值时不能算上自己。
$t$秒钟后，doyouloveme目测出了现在每只鸟的战斗力，于是感叹了一句：“不妙，我们得走了。”
正所谓团结的鸟儿一个顶俩，所以doyouloveme这样描述战斗力：一只鸟战斗力值等于它在$0$到$t$秒中士气值的最大值与团结值的最大值的乘积。注意不是乘积的最大值，而是最大值的乘积。
vfleaking很想知道现在每只鸟的战斗力，但是他当然不会啦，于是他把这个任务交给了你来完成。
小A的楼房外有一大片施工工地，工地上有N栋待建的楼房。每天，这片工地上的房子拆了又建、建了又拆。他经常无聊地看着窗外发呆，数自己能够看到多少栋房子。
为了简化问题，我们考虑这些事件发生在一个二维平面上。小A在平面上$(0,0)$点的位置，第$i$栋楼房可以用一条连接$(i,0)$和$(i,H_i)$的线段表示，其中$H_i$为第$i$栋楼房的高度。如果这栋楼房上任何一个高度大于$0$的点与$(0,0)$的连线没有与之前的线段相交，那么这栋楼房就被认为是可见的。
施工队的建造总共进行了$M$天。初始时，所有楼房都还没有开始建造，它们的高度均为$0$。在第$i$天，建筑队将会将横坐标为$X_i$的房屋的高度变为$Y_i$(高度可以比原来大，也可以比原来小，甚至可以保持不变)。请你帮小A数数每天在建筑队完工之后，他能看到多少栋楼房？
一个长度为$n$的大数，用$S_1S_2S_3\cdots S_n$表示，其中$S_i$表示数的第$i$位,$S_1$是数的最高位，告诉你一些限制条件，每个条件表示为四个数，$l_1,r_1,l_2,r_2$，即两个长度相同的区间，表示子串$S_{l_1}S_{l_1+1}S_{l_1+2}\cdots S_{r_1}$与$S_{l_2}S_{l_2+1}S_{l_2+2}\cdots S_{r_2}$完全相同。比如$n=6$时，某限制条件$l_1=1,r_1=3$，$l_2=4,r_2=6$，那么$123123,351351$均满足条件，但是$12012,131141$不满足条件，前者数的长度不为$6$，后者第二位与第五位不同。问满足以上所有条件的数有多少个。
Crash小朋友最近迷上了一款游戏——文明5(Civilization V)。在这个游戏中，玩家可以建立和发展自己的国家，通过外交和别的国家交流，或是通过战争征服别的国家。
现在Crash已经拥有了一个$N$个城市的国家，这些城市之间通过道路相连。由于建设道路是有花费的，因此Crash只修建了$N-1$条道路连接这些城市，不过可以保证任意两个城市都有路径相通。
在游戏中，Crash需要选择一个城市作为他的国家的首都，选择首都需要考虑很多指标，有一个指标是这样的：其中$S(i)$表示第$i$个城市的指标值，$dist(i,j)$表示第$i$个城市到第$j$个城市需要经过的道路条数的最小值，$k$为一个常数且为正整数。
因此Crash交给你一个简单的任务：给出城市之间的道路，对于每个城市，输出这个城市的指标值，由于指标值可能会很大，所以你只需要输出这个数$\bmod 10007$的值。
过不了多久，Crash就要迎来他朝思暮想的暑假。在这个暑假里，他计划着到火星上旅游。在火星上有$N$个旅游景点，Crash用$1$至$N$这$N$个正整数对这些景点标号。旅游景点之间通过双向道路相连。由于火星的环境和地球有很大的差异，建立道路的成本也相对较高。为了节约成本，只有$N-1$条道路连接着这些旅游景点，不过可以保证任何两个不同的旅游景点都通过路径相连。
Crash预先在互联网上查阅了这些景点的信息，根据网上的介绍，他对每个景点都有一个印象值，这个印象值为一个整数。在这个旅行中，他会选择一个景点作为旅行的开始，并沿着存在的道路到达其他景点游玩。为了使旅行不显得乏味，Crash不会经过同一个景点超过一次。Crash还给这次旅行定义了一个快乐指数，也就是他经过的所有景点的印象值之和。
不过Crash是个奇怪的小朋友，他对于景点的印象值会发生改变，并且他也没有决定好应该从哪个景点开始旅行。因此他希望你能写一个程序帮他完成一个简单的任务：根据当前他对每个景点的印象值，计算从某个景点开始旅行所能获得的最大的快乐指数。
测试数据分为$ABC$三类，对于所有的测试数据都满足：在任何时候一个景点印象值的绝对值不超过$10000$，并且输入的道路一定能满足题目描述的要求，即使得任意两个不同的景点都能通过路径相连。
对于$A$类数据（占20%的分数）满足：$N$和指令的条数都不超过$1000$。
对于$B$类数据（占40%的分数）满足：$N$和指令的条数都不超过$100000$，且输入的第$i$条道路，连接着$i$号景点和$i+1$号景点（详见样例2）。
对于$C$类数据（占40%的分数）满足：$N$和指令的条数都不超过$100000$，且任何一个景点到$1$号景点需要通过的道路条数不超过$40$。