问题1101--小邦打榜

1101: 小邦打榜

[命题人 : ]
时间限制 : 5.000 sec  内存限制 : 256 MB

提交

题目描述

HHU的小邦很喜欢打榜,他最爱的 Don 正在和 John 进行一场前所未有的大比拼。

这个比拼非常地复杂,共有m个子榜单,编号1到m,并且由于主办方的偏见,每个子榜单的分值都不一样。每个子榜单都会发放n个投票资格,编号为1到n。在子榜单中领先的人即可获得这个子榜单的全部分数。

由于一些规则,打榜行动也非常地复杂,每次打榜行动会有时刻 ts 和子榜单编号 b,打榜行动严格按照时间顺序给出,具体行动有以下几种(都是闭区间):

  • 1 l r Don/John :表示子榜单中编号在 l 到 r 的票全都投票给Don或者John,不论处在何种状态;

  • 2 l r :表示子榜单中编号在 l 到 r 的票全都撤销投票,即变为未投票状态,未投票状态的人仍然是未投票状态;

  • 3 l r :表示子榜单中编号在 l 到 r 的票全都反转,即投给Don的人变成了投给John,反之亦然,未投票状态的人仍然是未投票状态。

在初始时所有人都是未投票状态,现在小邦很想知道 Don 在总榜单中总共领先了多少时间,如果直到所有打榜行动结束 Don 仍然领先,则输出 "Don Win!"(不含引号)。

注意,在子榜单中只有得票严格大于对方才能算领先,同样地,在总榜单中只有得分严格大于对方才算领先。

输入

第一行一个整数T,表示接下来有T组数据。

每组数据第一行三个整数 m, n, p,分别表示子榜单、投票资格、打榜行动的数量。

第二行m个整数 si ,分别表示每个子榜单的分数。

接下来p行,每行五个整数 ts, b, type, l, r,分别表示时刻,子榜单编号,打榜行动的类型,区间的左右端点。如果 type=1,该行还会给出一个字符串。

1 <= T <= 13

1 <= m <= 25

1 <= n, p, si <= 10^5

1 <= ts <= 10^8

1 <= b <= m

1 <= l, r <= n

type ∈ {1, 2, 3}

数据保证组内每行的ts严格上升。



输出

对于每组数据输出一个数,表示Don 在总榜单中总共领先了多少时间,或者一个字符串 "Don Win!"(不含引号)

样例输入 Copy

2
1 2 1
10
1 1 1 1 1 Don
2 10 5
15 20
1 1 1 1 1 Don
2 2 1 1 1 John
3 2 2 1 5
6 1 1 1 8 John
9 1 3 1 4

样例输出 Copy

Don Win!
4

提示

若1时刻的打榜让Don领先而2时刻的打榜让Don不领先,则此时Don领先了1单位时间。

来源/分类