#P6866. 智者
智者
智者
题目描述
小 D 听了一个故事。
这个故事是著名的红蓝眼睛问题在更多颜色情况下的拓展(如果你并不清楚红蓝眼睛问题,这并不影响你做题):
在一个岛上,有个极端聪明的智者,每个人头上都有一个帽子,上面有一个介于 之间的数字。这里的数值范围限制输入,推理时不作为智者已知条件,候选帽子数字取全体整数。每个人能看到其他所有人帽子上面的数字,但是唯独看不到自己的。不会有任何两个智者交流与帽子上的数字有关的话题。
由于一些宗教因素,我们称一个 是合法的,当且仅当, 使得 ,或者 ,其中 和 都是给定的序列。智者们都已知现在的数字序列一定是合法的。
每天,如果存在一个智者,他知道了一个数字 ,使得 一定不为 ,那么他会立即宣布这一事件,并且这一过程结束。如果没有这样的智者, 那么这一天将会结束,并进入下一天。
小 D 想要知道,这个过程会在第几天结束,或者会永远进行下去。 但是小 D 并不会,请你帮帮他。
输入格式
从标准输入读入数据。
第一行一个正整数 ,表示智者的个数。 第二行个空格隔开的正整数,其中第个数为。 第三行 个整数,其中第个数为。 第四行 个整数,其中第个数为。
输出格式
向标准输出输出答案。
输出一行一个整数,表示结束的天数。特别地,如果永远不会结束,请输出
。
样例1输入
3
1 2 3
0 0
0 0
样例1输出
2
数据范围
对于所有测试数据,$1\le N\le 3\times 10^{5},1\le a_{i}\le 10^{5},-10^{5}\le b_{i},c_{i}\le 10^{5}$, 保证输入的 是合法的。
• Subtask 1(30%):;
• Subtask 2(40%):;
• Subtask 3(30%):无特殊限制。