跳到主要内容

题干汇总

· 阅读需 26 分钟

T1 琪亚娜与赤鸢​

题目描述​

“老古董，看看你干的好事！”

符华面无表情地转过身：“我又怎么了？”

“赤鸢！你的那群赤鸢全跑了！”

识之律者指着山下，声音顿时拔高了八度。

“那可是你的鸟！你的！你作为主人能不能上点心？它们就这么扑棱着翅膀飞走了，你居然还在这里站着？”

符华沉默了两秒。

“……赤鸢本就是自由的。”

“自由个鬼！”

识之律者差点跳起来。

“你当年养它们的时候可不是这么说的！‘赤鸢是我唯一的伙伴’——这话是谁说的？啊？现在它们跑了，你跟我说自由？”

恰好，琪亚娜路过太虚山。本着添乱帮助班长解决困难的想法，她自告奋勇地加入了赤鸢抓捕行动。

“班长你放心！不就是抓几只鸟吗？包在我身上！”

“琪亚娜，等等，那边是悬崖——”

“我当然知道！这只是战术迂回！”

……

经过一番极其激烈的追逐，她们终于抓回了所有逃走的赤鸢。

然而，新的问题很快出现了。

原本用来饲养赤鸢的围栏已经破得不成样子。在围栏修好之前，她们只能把赤鸢暂时安置在一个大小为 VV 的房间里。

可是赤鸢们刚刚获得自由，显然不愿意乖乖回到房间。每当一只赤鸢被送到门口时，它都会张开翅膀拼命挣扎，保持自己原本的大小 AiA_i。

因此，要将第 ii 只赤鸢送进房间，在它进入房间的那一刻，房间中剩余的空间必须至少为 AiA_i。否则，无论琪亚娜怎么推，它都不可能穿过房门。

“让我来！我最擅长说服别人了！”

识之律者挽起袖子，在这只赤鸢进入房间后，狠狠地给了它一下。

于是，原本还在扑腾的赤鸢立刻安静下来，并被打扁成了大小为 BiB_i 的一团。此后，只要它仍待在房间中，就只会占据 BiB_i 的空间。

换句话说，如果送入第 ii 只赤鸢之前，房间中已有的赤鸢共占据 SS 的空间，那么必须满足

S+Ai≤V.S+A_i\le V.

当它被成功送入并打扁后，房间中所有赤鸢占据的空间将变为

S+Bi.S+B_i.

已经放入房间的赤鸢不会被取出，而尚未放入的赤鸢可以按照任意顺序进行尝试。不过，房间终究只有这么大，并不是所有赤鸢都一定能够被安置进去。

符华看着满地乱跑的赤鸢，陷入了沉思。

“或许，我们应该先决定将哪些赤鸢放进去。”

“还要决定顺序！”琪亚娜补充道，“有些赤鸢现在看起来很大，被小识打扁以后却只占一点地方。要是顺序不对，后面的可能就塞不进去了！”

“哼，这种小事怎么可能难得倒我？我可是伟大的识之律者女士！”

小识盯着赤鸢们看了许久，最后默默地转向了身为舰长兼 Oier 的你。

请你从这 NN 只赤鸢中选择尽可能多的赤鸢，并为被选择的赤鸢安排一种可行的放入顺序，使它们都能顺利进入房间。

你只需要指出哪些赤鸢应当被放入房间，不需要输出具体顺序。只要被选择的赤鸢之间存在至少一种满足要求的放入顺序，这组方案就是合法的。

至于那些实在放不进去的赤鸢，就暂时交给琪亚娜带回去照顾吧。

希望休伯利安的伙食费还能撑得住。

输入格式​

输入包括 33 行。

输入的第一行包含 NN 和 VV ，表示跑掉的赤鸢数量和房间的大小。

接下来的 11 行包括 NN 个整数，表示每只赤鸢原来的大小 AiA_i。

接下来的 11 行包括 NN 个整数，表示每只赤鸢被打后的大小 BiB_i。

输出格式​

输出包括 22 行。

第一行包括一个整数 KK，表示能放进去的最大赤鸢数量。

第二行包括 NN 个 1/0，表示第 ii 只赤鸢选/不选放入房间，输出满足条件的任意一组解即可。

输入输出样例 #1​

输入 #1​

4 10
6 5 4 7
2 3 2 4

输出 #1​

3
1 1 1 0

选择第 1,2,31,2,3 只赤鸢，依次放入并打扁后，占用空间分别为 2,5,72,5,7 可以全部放入房间。

输入输出样例 #2​

输入 #2​

5 12
8 7 5 4 6
3 5 2 2 4

输出 #2​

3
1 0 1 1 0

选择第 4,3,14,3,1 只赤鸢，依次放入并打扁后，占用空间分别为 2,4,72,4,7 可以全部放入房间。

说明/提示​

1≤N≤2×105,1≤K≤2×1018,1≤Bi≤Ai≤2×10151 \le N \le 2 \times 10^5,1 \le K \le 2 \times 10^{18},1 \le B_i \le A_i \le 2 \times 10^{15}。

对于 10%10\% 的测试点，满足 1≤N≤201 \le N \le 20。

对于 30%30\% 的测试点，满足 1≤N≤2×1031 \le N \le 2 \times 10^3。

对于其中 5%5\% 的测试点，额外满足性质 Ai=BiA_i=B_i。

对于 60%60\% 的测试点，满足 1≤N≤2×1051 \le N \le 2 \times 10^5。

小识：造数据的就是个废物，怎么一堆错误解法能骗过去。

T2 琪亚娜与虚数之海​

题目描述​

虚数之海开花了！

沉没在海底的世界泡残骸上，开出了一朵朵由数据构成的小花。它们在黯淡的海面下轻轻摇曳，像是那些早已消逝的世界留下的最后一场梦。

“布洛妮娅，你说这里的花是什么样子的啊？我还没听说过虚数之海里也会开花呢！”

“笨蛋琪亚娜，你已经在布洛妮娅耳边说了一整路了。”

“可是这里到处都长得一样嘛。万一我们走散了怎么办？”

“以琪亚娜的智商，就算没有走散，也有很大概率迷路。”

“喂！”

“重装小兔 0019C，变形。”

“欸，等等我啊！！！布洛妮娅！”

伴随着引擎的轰鸣声，布洛妮娅很快消失在了虚数之海的深处。

“……不对，这里应该怎么走来着？”

收到希儿的邀请后，琪亚娜和布洛妮娅一同踏上了前往虚数之海赏花的旅途。然而，因为琪亚娜实在太话痨可爱，布洛妮娅决定骑着重装小兔先走一步。

于是，原地只剩下琪亚娜，以及一张她似乎完全看不懂的地图。

“冷静，琪亚娜。你可是拯救过世界的人，区区一张地图而已……”

琪亚娜盯着地图看了很久。

“这个箭头到底是什么意思啊？”

好在，凭借她金鱼一般惊人的记忆力，琪亚娜还是想起了布洛妮娅之前说过的话。

虚数之海中散落着 NN 个世界泡残骸，编号为 11 到 NN。第 ii 个世界泡残骸上，生长着 WiW_i 朵由数据构成的花。

不同的世界泡残骸之间存在着被称作“蚀洞”的通道。蚀洞中的空间流动具有固定方向：如果地图上记录着一个从世界泡 uu 指向世界泡 vv 的蚀洞，琪亚娜就可以借助它从 uu 前往 vv，却未必能从 vv 沿着同一个蚀洞返回 uu。

每当琪亚娜第一次抵达一个世界泡时，那里的花便会在她的终端中留下数据。终端会自动排除重复记录，因此以后即使她再次来到这里，也不会让已经记录过的花再被计算一次。

蚀洞并不会因为通行而消失。只要方向允许，琪亚娜可以多次穿过同一个蚀洞，也可以多次回到曾经到过的世界泡。

现在，琪亚娜位于编号为 11 的世界泡中。除了手里的地图和各个世界泡中花的数量，她已经完全不记得希儿究竟在哪个方向了。

“既然已经找不到路了，那就干脆多看一些花吧！”

输入格式​

输入的第一行包含 NN 和 MM ，表示世界泡残骸的数量和蚀洞的数量。

接下来的 11 行包括 NN 个正整数 WiW_i，表示第 ii 个世界泡残骸上长出的花的数量。

接下来 MM 行每行包括两个整数 u,vu,v，表示第 uu 个世界泡残骸到第 vv 个世界泡残骸有一个蚀洞。

输出格式​

输出只包含一个整数，表示能看到的最多花的数量。

你不需要在意她最后到了哪个点上，因为她大可直接穿过虚数之海回月球。

输入输出样例 #1​

输入 #1​

5 6
3 2 5 4 6
1 2
1 3
2 4
3 4
3 5
4 5

输出 #1​

18

输入输出样例 #2​

输入 #2​

6 5
10 1 7 20 3 100
1 2
1 3
3 4
2 5
5 6

输出 #2​

114

说明/提示​

1≤N1×≤105,1≤M≤1×106,1≤Wi≤1e91 \le N 1 \times \le 10^5,1 \le M \le 1 \times 10^6,1 \le W_i \le 1e9。

对于 10%10\% 的测试点，满足性质 M=N−1M=N-1。

对于 10%10\% 的测试点，满足性质 N=MN=M。

保证从第 11 个世界泡残骸可以到达任意一个世界泡残骸。

布洛妮娅：作为一位智慧的 Oier，你应该能注意到这个题要开大栈空间吧。

T3 琪亚娜与小蛋糕​

题目描述​

“真好吃啊，谢谢芽衣！”

琪亚娜坐在桌前，幸福地吃着芽衣亲手做的小蛋糕。柔软的奶油与恰到好处的甜味在口中化开，让她完全没有注意到，芽衣温柔的目光中，除了宠溺，似乎还藏着一丝不太一样的感情……

“琪亚娜，吃饱了吗？”

“唔……吃饱了！”

刚刚咽下最后一块蛋糕的琪亚娜抬起头，恰好对上芽衣的眼睛。

那双眼眸炽热而渴望。

气氛好像有些不对。

琪亚娜突然回想起了一些不太妙的事情。

“等等，芽衣，你听我解释，我突然想起来月球基地还有非常重要的任务！”

意识到大事不妙，琪亚娜起身就跑。可是她才迈出几步，肚子里便传来了一阵沉重的饱腹感。

“咕唔……刚才好像吃得太多了，根本跑不动啊！”

由于吃得实在太快，蛋糕带来的饱腹感并不会立刻出现，而是会在琪亚娜逃跑路过某些山峰时突然结算。

芽衣一共准备了 NN 个小蛋糕，编号为 11 到 NN。第 ii 个蛋糕拥有美味值 AiA_i 与甜蜜值 BiB_i。

琪亚娜不一定要吃下所有蛋糕，但她只能按照编号从小到大的顺序选择它们。假设她依次选择了编号为

p1<p2<⋯<pkp_1<p_2<\cdots<p_k

的蛋糕。

第一块被吃掉的蛋糕还没有受到其他味道的影响，因此会为她带来 Ap1A_{p_1} 点美味。

从第二块蛋糕开始，前一块蛋糕残留在口中的甜蜜会与当前蛋糕的味道交融。若琪亚娜刚刚吃过编号为 pt−1p_{t-1} 的蛋糕，接着又吃下编号为 ptp_t 的蛋糕，那么这一次会为她带来

Bpt−1×AptB_{p_{t-1}}\times A_{p_t}

点美味。

于是，这种吃法最终带来的美味值总和为

Ap1+∑t=2kBpt−1Apt.A_{p_1}+\sum_{t=2}^{k}B_{p_{t-1}}A_{p_t}.

对于每个 ii，琪亚娜的终端都会计算：在最后吃下第 ii 个蛋糕的前提下，她最多能够获得多少美味值。记这个数为 FiF_i。

然而，当琪亚娜逃出门时才发现，通往月球基地的传送装置竟然被布洛妮娅安装在了第 NN 座山上。

“为什么会有人把传送装置放在山顶啊！”

“为了防止草履虫擅自使用。”

终端中传来了布洛妮娅毫无波澜的声音。

从太虚山到月球基地的途中共有 NN 座山，编号同样为 11 到 NN。琪亚娜最初位于第 11 座山，而传送装置位于第 NN 座山。

她每次可以从当前所在的第 ii 座山直接前往任意一座编号更大的山 jj。奇怪的是，当她抵达第 ii 座山时，她的饱腹感恰好会变成 FiF_i。

饱腹感变化得越剧烈，琪亚娜就越难继续奔跑。从第 ii 座山前往第 jj 座山，需要花费的时间为

(Fj−Fi)2.(F_j-F_i)^2.

她可以跳过途中任意数量的山，但不能返回编号更小的山。琪亚娜需要自行决定经过哪些山峰，并最终到达第 NN 座山。

此时，芽衣的声音已经从身后传来。

“琪亚娜，跑这么快做什么？”

“没、没什么！我只是突然想去月球看看风景！”

为了尽快启动传送装置，琪亚娜需要知道两件事：

  • 最后吃下第 NN 个蛋糕时，能够获得的最大美味值 FNF_N；
  • 从第 11 座山出发并到达第 NN 座山，最少需要花费多少时间。

请你帮助琪亚娜计算这两个答案。

至于“小蛋糕”究竟指什么，琪亚娜决定还是不要继续想下去了。

输入格式​

输入包括 33 行。

第一行包括 NN，表示蛋糕和山的个数。

第二行包括 NN 个整数 AiA_i，表示第 ii 个蛋糕的美味值。

第二行包括 NN 个整数 BiB_i，表示第 ii 个蛋糕的甜蜜值。

因为芽衣本来就想要琪亚娜多吃蛋糕，所以美味值和甜蜜值是递增的。

输出格式​

输出包括 22 行。

第一行包括 11 个整数，表示吃第 NN 个蛋糕能得到的最大美味值总和。

第二行包括 11 个整数，表示到达第 NN 座山时的最小时间。

如果你输出的第一行正确可以得到 30%30\%的分数。

输入输出样例 #1​

输入 #1​

6
1 3 5 7 9 11
2 3 5 7 8 9

输出 #1​

208
13199

说明/提示​

1≤N≤2×105,1≤Ai,Bi≤5×1061 \le N \le 2 \times 10^5,1 \le A_i,B_i \le 5 \times 10^6。

对于 20%20\% 的测试点，满足性质 1≤N≤1×1031 \le N \le 1 \times 10^3。

对于 10%10\% 的测试点，满足所有的 AiA_i 全部相等。

芽衣：最后的答案都要开 int128int128 了，琪亚娜是肯定跑不掉的。

//int128 的读入
inline __int128 read()
{
    __int128 w=0;
    char ch=getchar();
    while( isdigit( ch ) )
    {
        w=w*10+ch-'0';
        ch=getchar();
    }
    return w;
}

inline void print( __int128 num )
{
    if( num > 9 ) print( num/10 );
    putchar( num%10+'0' );
}

//比较int128乘积用, a*b <= c*d
#define QAQ return
#define intt __int128
#define ull unsigned long long
#define uintt unsigned __int128

inline void mul128( uintt a,uintt b,uintt &hi,uintt &lo )
{
    ull al=( ull )a, ah=( ull )( a>>64 );
    ull bl=( ull )b, bh=( ull )( b>>64 );
    uintt p00=( uintt )al*bl;
    uintt p01=( uintt )al*bh;
    uintt p10=( uintt )ah*bl;
    uintt p11=( uintt )ah*bh;
    uintt mid=( p00>>64 )+( ull )p01+( ull )p10;
    lo=( p00&( ( ( uintt )1<<64 )-1 ) )|( mid<<64 );
    hi=p11+( p01>>64 )+( p10>>64 )+( mid>>64 );
}

inline bool mul_leq( intt a,intt b,intt c,intt d )
{
    int s1=( a<0 )^( b<0 );
    int s2=( c<0 )^( d<0 );
    if( s1 != s2 ) QAQ s1 > s2;
    uintt ua=( a < 0 ? ( uintt )-( a+1 )+1 : ( uintt )a );
    uintt ub=( b < 0 ? ( uintt )-( b+1 )+1 : ( uintt )b );
    uintt uc=( c < 0 ? ( uintt )-( c+1 )+1 : ( uintt )c );
    uintt ud=( d < 0 ? ( uintt )-( d+1 )+1 : ( uintt )d );
    uintt hi1,lo1,hi2,lo2;
    mul128( ua,ub,hi1,lo1 );
    mul128( uc,ud,hi2,lo2 );
    bool abs_leq=( hi1 != hi2 ? hi1 < hi2 : lo1 <= lo2 );
    QAQ ( s1 ? !abs_leq : abs_leq );
}

T4 琪亚娜与送货​

题目描述​

题目描述​

一年一度的月球节到了！

“姨妈，你看，可爱吧！”

琪亚娜兴冲冲地闯进办公室，将一个抱着苦瓜的小玩偶举到了德丽莎面前。

玩偶有着白色的头发、蓝色的眼睛和一张气鼓鼓的小脸，就连怀里的苦瓜都做得惟妙惟肖。

“今年月球节，大家都开始收集德丽傻玩偶了！这个活动还是我想出来的呢！”

办公室里陷入了短暂的沉默。

“……琪亚娜。”

“怎么了，姨妈？”

“第一，不许叫我德丽傻。”

“好嘞，德丽莎学院长！”

“第二，为什么这个玩偶抱着苦瓜？”

“因为很符合姨妈的形象啊！”

“第三——犹大，展开！”

……

虽然被德丽莎赶出了办公室，还结结实实地挨了犹大一下，但琪亚娜最终还是成功申请到了“德丽傻大收集”活动的奖品资助。

至于派送奖品的任务，不知道是因为德丽莎的命令，还是某位出题人的恶趣味，最后也落到了琪亚娜身上。

月球上共有 NN 位居民，编号为 11 到 NN。居民之间有 N−1N-1 条道路，并且任意两位居民之间都能通过这些道路互相到达。

换句话说，所有居民及道路共同构成了一棵树。

活动开始时，第 ii 位居民拥有 WiW_i 个德丽傻玩偶。随着活动进行，某些居民还可能获得更多德丽傻玩偶。

“都说了那不是德丽傻！”

“姨妈，现在改活动名称已经来不及啦！”

为了鼓励大家收集玩偶，琪亚娜设计了一种组队兑换活动。

每场兑换活动会由两位居民 uu 和 vv 发起。除了这两位居民，从 uu 到 vv 的简单路径上经过的所有居民也会自动加入队伍。

活动还会给出一个门槛 upperupper。对于这支队伍中的每位居民，如果其当前拥有的德丽傻玩偶数量不少于 upperupper，那么这位居民就会为本场活动提供 11 点贡献。

设本场活动获得的总贡献为 cntcnt，即

cnt=∣{x∣x 位于 u 到 v 的简单路径上，且 Wx≥upper}∣.cnt= \left|\left\{ x\mid x\text{ 位于 }u\text{ 到 }v\text{ 的简单路径上，且 }W_x\ge upper \right\}\right|.

随后，队伍中的每一位居民都会得到 cntcnt 个琪亚娜玩偶作为奖品。

这些琪亚娜玩偶只用于统计活动奖品，不会改变居民拥有的德丽傻玩偶数量，也不会影响之后活动中的贡献判定。

例如，某场活动的队伍中共有五位居民，其中三位居民当前拥有的德丽傻玩偶数量不少于门槛，那么本场活动的总贡献就是 33。这五位居民将各自获得 33 个琪亚娜玩偶。

“也就是说，大家收集的德丽傻越多，我就要送出去越多自己的玩偶？”

“琪亚娜，你终于发现了吗？”

“等等，这个活动是不是有哪里不太对……”

除了兑换活动，活动期间还会发生另一种事件：某位居民 xx 又获得了 yy 个德丽傻玩偶。发生这种事件后，需要立即令

Wx←Wx+y.W_x\leftarrow W_x+y.

新的数量会影响此后所有兑换活动中的贡献判定，但不会改变已经结束的活动及其奖品。

为了防止有人偷看活动记录，布洛妮娅还对每场兑换活动的门槛进行了加密。

设上一场兑换活动得到的总贡献为 lastlast。读入一场兑换活动所给出的门槛 upperupper 后，必须先执行

upper←upperxor⁡last,upper\leftarrow upper\mathbin{\operatorname{xor}}last,

再使用解密后的 upperupper 进行贡献判定。

在第一场兑换活动开始前，规定

last=0.last=0.

每场兑换活动结束后，再令 lastlast 等于本场活动得到的总贡献。居民获得德丽傻玩偶的事件不需要解密，也不会改变 lastlast。

活动期间发生的所有事件必须严格按照给出的顺序处理。

然而，琪亚娜嫌来回送货实在太麻烦，便决定先把所有奖品堆在仓库里，等活动结束后再一次性送出。

结果，她一个玩偶也没有及时送。

直到月球节结束，琪亚娜看着堆满仓库的纸箱，才猛然想起自己还没有统计每位居民究竟应该获得多少奖品。

“这么多活动记录，真的要一条一条算吗……”

“琪亚娜，这是你自己设计的活动。”

“所以我这不是来找舰长帮忙了吗！”

好在，所有居民最初拥有的玩偶数量、道路信息以及活动期间发生的事件都被完整地保存了下来。

请你按照时间顺序还原整个活动，计算活动结束后每位居民总共应当得到多少个琪亚娜玩偶。

输入格式​

第一行包括 11 个整数 NN，表示居民的个数。

接下来一行包括 NN 个整数 WiW_i，表示每个居民持有的德丽傻玩偶数量。

接下来 N−1N-1 行每行包括两个整数 u,vu,v，表示居民 uu 和居民 vv 之间有一条路径。

第 N+2N+2 行包括 11 个整数 QQ，表示活动参与的信息。

接下来 QQ 行每行一个操作，为以下两种之一

  1. 1, x, y1,\ x,\ y，表示第 xx 个居民又获得了 yy 个德丽傻玩偶。

  2. 2, u, v, upper2,\ u,\ v,\ upper，表示 uu 和 vv 报名了一场限制为 upperupper 的兑换活动。

注意：22 询问读入 upperupper 之后要和上次 22 询问得到的贡献做一次异或来解密，但是 11 询问不需要。

保证每个居民的德丽傻数量不会超过 1×1051 \times 10^5

cin>>u>>v>>upper;
upper^=cnt;
do...
cnt=本次查询每个点需要增加的值

输出格式​

输出包括 11 行 NN 个整数表示每个居民得到的琪亚娜玩偶数量。

输入输出样例 #1​

输入 #1​

5
2 3 4 5 6
1 2
1 3
2 4
3 5
4
2 4 5 4
1 2 2
2 2 5 6
2 1 4 0

输出 #1​

8 8 5 6 5

说明/提示​

1≤N,Q≤1×105,1≤Wi,X≤1×105,1≤u,v≤N1 \le N, Q \le 1 \times 10^5,1 \le W_i, X \le 1 \times 10^5, 1 \le u,v \le N。

对于 20%20\% 的测试点，满足性质 1≤N,Q≤1×1031 \le N, Q \le 1 \times 10^3。

对于 10%10\% 的测试点，保证给出的是一条链。

琪亚娜：毒瘤出题人太讨厌了，常数太大都不行！

琪亚娜与豆腐脑​

题目描述​

圣芙蕾雅学园一年一度的豆腐脑节即将开幕！

“芽衣！布洛妮娅！你们快来评评理！”

琪亚娜端着两碗豆腐脑冲进食堂，一碗撒满了糖，另一碗飘着葱花和酱油。

“豆腐脑当然应该是甜的！”

布洛妮娅面无表情地看了一眼桌子：“琪亚娜，根据布洛妮娅的观察，你刚刚把糖撒进了咸豆腐脑里，又把酱油倒进了甜豆腐脑里。布洛妮娅建议你先停止制造新的争执。”

“这、这是战术调配！”

“笨蛋琪亚娜，你的计算技巧确实数一数二——只不过是倒着数。连豆腐脑节的人员安排都没搞定，就不要给食堂增加变量了。”

原来，今年豆腐脑节共有 nn 位参与者。每个人都需要在活动开始前表明自己的立场：支持甜豆腐脑，或者支持咸豆腐脑。

参与者分为三类：

  • 甜党：必须支持甜豆腐脑；

  • 咸党：必须支持咸豆腐脑；

  • 中立派：可以自行选择支持其中一方。

但立场不是白站的。第 ii 位参与者如果选择支持甜豆腐脑，需要支付 aia_i 的准备费用；如果选择支持咸豆腐脑，需要支付 bib_i。

更麻烦的是，参与者之间存在 mm 条有向争执关系。一条关系 (u,v,w)(u,v,w) 表示：

如果参与者 uu 支持甜豆腐脑，而参与者 vv 支持咸豆腐脑，那么两人之间会产生 ww 的调解费用。

其他立场组合不会触发这条关系的费用，毕竟同好之间有什么可吵的呢。

“让我来！我只要把所有人随便一分——”

“琪亚娜，布洛妮娅提醒你，随便分会导致活动预算爆炸。而且你刚刚把甜党分到了咸党那边。”

“那、那只是战术性失误！”

“舰长！你来得正好！快帮我们安排中立派的立场，在满足甜党和咸党立场限制的前提下，让所有人的准备费用与争执调解费用之和最小！”

布洛妮娅合上终端，补充道：“布洛妮娅已经把问题整理好了。你需要安排所有中立派的立场，使得在满足甜党和咸党立场限制的前提下，所有参与者的准备费用与争执调解费用之和最小。”

琪亚娜连连点头：“对对对，就是这个！至于我负责什么——”

“琪亚娜负责不要继续把糖倒进咸豆腐脑里。”

“喂！”

输入格式​

第一行包括两个整数 NN 和 MM，分别表示参与者的数量和争执关系的对数。

第二行包括 NN 个整数，每个数是 0,1,2 中的一个，表示第 ii 位参与者是甜党，咸党或中立派。

接下来 NN 行每行包括 22 个整数，第 ii 行表示参与者 ii 支持甜豆腐脑的费用 aia_i 和支持咸豆腐脑的费用 bib_i。

接下来 MM 行每行包括 33 个整数 u,v,wu,v,w 用来描述一组争执关系。

输出格式​

输出只包含一个整数，表示分配的最小费用。

输入输出样例 #1​

输入 #1​

4 3
0 1 2 2
10 100
100 10
5 20
15 3
1 3 100
1 4 5
2 3 50

输出 #1​

28

说明/提示​

1≤N≤3×103,1≤M≤2×104,1≤u,v≤N,u≠v,1≤w≤1×1091 \le N \le 3 \times 10^3,1 \le M \le 2 \times 10^4, 1 \le u,v \le N,u \ne v,1 \le w \le 1 \times 10^9。

对于 10%10\% 的测试点，满足 N≤16N \le 16

对于 10%10\% 的测试点，满足 n=m−1n = m-1。

琪亚娜与OSU!​

题目描述​

琪亚娜最近痴迷于 OSU!OSU!。她想写一套“观赏谱”，用来纪念某个不能忘记的人。

琪亚娜将 NN 个音铃首尾相接摆成一个环，并依次编号为 0,1,…,N−10,1,\ldots,N-1。

一枚“引子印” SS 是由环上若干个音铃组成的非空集合。记 d=∣S∣d=|S| 为这枚引子印的点数。

对于一枚点数为 dd 的引子印，琪亚娜按照如下规则在环上行走：

从任意音铃 ii 出发，每次从当前音铃 xx 走到

(x+d) mod N,(x+d)\bmod N,

并不断重复这一过程，直到第一次回到出发的音铃 ii。在这一过程中经过的所有音铃组成一段“环音律”。

如果两次行走经过的音铃集合完全相同，仅出发位置不同，则它们被视为同一段环音律。

对于引子印 SS，考虑从环上每个音铃出发得到的环音律，其中互不相同的环音律数量称为 SS 的环数。等价地，环数就是覆盖全部 NN 个音铃所需的最少环音律段数。

如果引子印 SS 的环数恰好等于它的点数，即

环数=∣S∣,\text{环数}=|S|,

那么称 SS 是一张合法的“琪谱”。

两张琪谱是否不同，只由它们对应的引子印集合决定。只要两个引子印包含的音铃不同，它们就被视为两张不同的琪谱。

琪亚娜需要为每一张合法琪谱分别选择一种主题。共有 QQ 种主题可供选择，不同琪谱可以使用相同的主题。

一种“带主题的谱集”是指对所有合法琪谱各自指定一种主题。只要至少有一张琪谱所选择的主题不同，就视为两种不同的谱集。

请计算带主题的谱集总数对 MM 取模后的结果。

保证 MM 是质数，并且

∣μ(M−1)∣=1.|\mu(M-1)|=1.

此外，若 M>2M>2，保证 M−1M-1 的最大质因数不超过 2×1062\times 10^6。

输入格式​

输入包括一行 33 个整数 N,Q,MN,Q,M，分别表示音铃数，主题数和取模的数。

输出格式​

输出包括一行 11 个整数，表示总方案数对 MM 取模后的答案

输入输出样例 #1​

输入 #1​

5 2 7

输出 #1​

1

说明/提示​

1≤N,Q≤1×1012,1≤M≤1×1091 \le N, Q \le 1 \times 10^12,1 \le M \le 1 \times 10^9。

对于 5%5\% 的测试点，满足 N≤18,M≤103N \le 18, M\le 10^3。

对于 10%10\% 的测试点，满足 N≤103,M≤105N \le 10^3, M\le 10^5。

对于 5%5\% 的测试点，满足 NN 是质数。

对于 30%30\% 的测试点，满足 M=3M = 3。

如果你不知道莫比乌斯函数：

  • 如果 n=1n = 1，则 μ(n)=1\mu(n) = 1。

  • 如果 nn 的因子中有大于 11 的平方数，则 μ(n)=0\mu(n) = 0。

  • 如果 nn 是无平方因子的数，且 nn 是 kk 个质数的积，也就是 n=p1×p2×⋯×pkn = p_1 \times p_2 \times \cdots \times p_k，其中 pip_i 是互不相同的质数，则 μ(n)=(−1)k\mu(n) = (-1)^k。