Migrated from Lutece 2924 导航系统

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Tag:线段树/树状数组+分类讨论

T国是一个由$n$个岛屿构成的岛国，这$n$个岛屿编号从$1$到$n$。为了使得岛屿之间互相连通，国王下令在岛屿间修建了$n$座桥：对于$1\le i< n$，第$i$座桥连接$i$号岛屿和$i+1$号岛屿，而第$n$座桥则连接了$n$号岛屿和$1$号岛屿。简单来说，这$n$个岛屿构成了一个环。通过其中第$i$座桥需要花费$a_i$的时间，桥为双向通行。为与后文区别，我们称呼这些桥为“老桥”。

可是由于海啸频繁，一些桥将暂时陷入瘫痪，此时这座桥将无法通过。显然当$2$座及以上的桥陷入瘫痪时，这$n$座岛屿将不再相互连通。对于如此不便利的交通条件，居民们常常怨声载道。

面对这日益增长的压力，国王决定另外修建$m$个人工岛屿和$m+1$座桥来缓解这一状况，这$m$个人工岛屿编号从$n+1$到$n+m$。在这$m+1$座新修的桥中，对于$1< i\leq m$，第$i$座桥连接了$n+i-1$号人工岛屿和$n+i$号人工岛屿；而第$1$座桥则连接了$1$号岛屿和$n+1$号人工岛屿，第$m+1$座桥则连接了$n+m$号人工岛屿和S号岛屿（保证S号岛屿不是人工岛屿）。通过新修建的这$m+1$座桥中第i座桥的需要花费时间$b_i$，桥为双向通行。为与前文区别，我们称呼这些桥为"新桥"。

同时，为了帮助居民更好地选择从某一个岛屿到另一个岛屿的最佳路线，国王委托你实现一个导航系统，告诉居民从一个岛屿到另一个岛屿所需的最短时间（仅考虑经过所有桥花费的时间）。

由于海啸频繁，有时会出现某一座桥陷入瘫痪的情况。状况缓解时，已经瘫痪的桥也可能在某一时刻恢复正常使用。你实现的系统当然也需要考虑这些情况。

Input

第一行是三个整数$n,S,m$。
第二行是$n$个整数，第$i$个整数表示$a_i$。
第三行是$m+1$个整数，第$i$个整数表示$b_i$。
第四行只有一个整数$q$，表示接下来将会发生$q$个事件。
接下来$q$行，每一行描述一个事件，每一个事件由若干个整数描述。
对于每一个事件，第一个整数是$opt$。

• 若$opt=1$，则接下来两个整数$u$和$v$描述了一次询问，表示有居民询问了在当前情况下从$u$到$v$的最短时间。
• 若$opt=2$，则接下来一个整数$x$表示第$x$座老桥状态发生了变化。如果这座桥原本处于瘫痪状态，则它在这一时刻恢复正常；如果这座桥原本处于正常状态，则它在这一时刻因为海啸陷入了瘫痪状态。
• 若$opt=3$，则接下来一个整数$x$表示第$x$座新桥状态发生了变化。如果这座桥原本处于瘫痪状态，则它在这一时刻恢复正常；如果这座桥原本处于正常状态，则它在这一时刻因为海啸陷入了瘫痪状态。

Output

对于事件中的每一个询问，输出一行。

如果在当前状况下$u$可以到达$v$，则本行输出一个整数表示从$u$到$v$的最短时间。
如果在当前状态下$u$不能到达$v$，则本行输出"Pigs might fly!"(输出不包括双引号)。

Samples

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

6
10
16
Pigs might fly!

Constraints

$1<S\le n$，$1\le n,m\le 10^6$
$1\le a_i,b_i\le 200$
$1\le q\le 10^6$
$opt=1,2,3$
$1\le u,v\le n+m$
$1\le x\le n$ when $opt=2$
$1\le x\le m+1$ when $opt=3$

Resources

2023 UESTC ICPC Training for Data Structures