# Endless Punishment

Time Limit: 30000/15000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 95 Accepted Submission(s): 41

Problem Description

In the ancient Greek tale, Sisyphus was a king of Ephyra, he was punished for chronic deceitfulness by being compelled to roll an immense stone up a hill every day, only to watch it roll back down, and to repeat this action forever. Zeus, the God of the universe, shows some mercy for Sisyphus, so he decides to change the way of punishment. He puts N stones with the color of white or black in a line on the hill, everyday when Sisyphus rolls a new stone up the hill, the new stone is added to the back of the old N stones, and the first stone rolls down to the foot of the hill. Then Zeus shows his magic to change the color of the new N stones. Firstly, he looks at a subset S1 of the original N stones, which always includes the first stone, if an odd number of the stones are black, then the newly N-th stone will be black and white otherwise. After the first step is done, he flips the color of another subset S2 of the new N stones, black stone will become white, and white stone will become black vice versa. The following example illustrates how Zeus’s magic works. Consider the case of N = 4, S1 = {1,3}, S2 = {2,4}. Suppose the current stone color state is ●○○○, (○ for white stone, and ● for black stone), the 1st and 3rd stone is black and white respectively, so the new 4th stone will be black, produces ○○○● after the first step. At the second step, the 2nd and 4th stone flip its color, produces ○●○○ in the end. Zeus tells to Sisyphus that, if one day after the two steps are done, the color of the stones turns to one specific state, he will get his freedom. Now given the current and final stone colors, please compute how many days are needed for Sisyphus’s freedom?

Input

There are several test cases, please process till EOF. For each test case, the first line contains three integers, the first integer is N(2 ≤ N ≤ 31), the number of stones, followed by two integers S1 and S2, (1 ≤ S1,S2 ≤ N), denoting the size of two subsets as mentioned above. The second and third line contains S1 and S2 integers a and b in the increasing order, describing the two subsets. It is guaranteed that a1 always equals to 1. The last two lines each contains N integers with 0 (for white), or 1 (for black) denoting the current and final state. The first integer describes the first stone, and the last integer describes the last stone. Please note that there are about 500 test cases, fortunately, only 20 of them are big test cases.

Output

For each test case, output a single integer, the minimum days for Sisyphus to get his freedom. If Zeus is an absolute liar, then just simply print the sentence poor sisyphus.

Sample Input

4 2 2 1 3 2 4 1 0 0 0 0 1 0 0 4 2 2 1 3 2 4 1 1 1 1 0 0 0 0 4 2 2 1 3 2 4 1 1 1 1 0 1 0 0 10 5 6 1 2 4 5 6 2 4 5 8 9 10 0 0 0 0 0 0 1 0 0 0 1 1 1 1 1 1 1 1 1 1

Sample Output

1 4 poor sisyphus 387

Author

Fudan University

Source

2014 Multi-University Training Contest 3

### 题意很清楚。N(2 ≤ N ≤ 31)个01串，按照规则去变化，问经过几步可以从原串变化到目标串。

------ 本文结束------
• 本文作者： kuangbin
• 本文链接： 306.html
• 版权声明： 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处！
0%