A8654. Xor
编程题
普及/提高-
知识点
题目描述
John Doe has four arrays: $a$ , $b$ , $k$ , and $p$ . Each array consists of $n$ integers. Elements of all arrays are indexed starting from $1$ . Array $p$ is a permutation of integers $1$ to $n$ .
John invented a game for his friends and himself. Initially a player is given array $a$ . The player must consecutively execute exactly $u$ operations on $a$ . You are permitted to execute the following operations:
- Operation 1: For each  change $a_{i}$ into . Expression  means applying the operation of a bitwise xor to numbers $x$ and $y$ . The given operation exists in all modern programming languages, for example, in language C++ and Java it is marked as "^", in Pascal — as "xor".
- Operation 2: For each  change $a_{i}$ into $a_{pi}+r$ . When this operation is executed, all changes are made at the same time.
After all $u$ operations are applied, the number of points the player gets is determined by the formula .
John wants to find out what maximum number of points a player can win in his game. Help him.
John invented a game for his friends and himself. Initially a player is given array $a$ . The player must consecutively execute exactly $u$ operations on $a$ . You are permitted to execute the following operations:
- Operation 1: For each  change $a_{i}$ into . Expression  means applying the operation of a bitwise xor to numbers $x$ and $y$ . The given operation exists in all modern programming languages, for example, in language C++ and Java it is marked as "^", in Pascal — as "xor".
- Operation 2: For each  change $a_{i}$ into $a_{pi}+r$ . When this operation is executed, all changes are made at the same time.
After all $u$ operations are applied, the number of points the player gets is determined by the formula .
John wants to find out what maximum number of points a player can win in his game. Help him.
输入格式
The first line contains space-separated integers $n$ , $u$ and $r$ ( $1<=n,u<=30$ , $0<=r<=100$ ) — the number of elements in each array, the number of operations and the number that describes one of the operations.
Each of the next four lines contains $n$ space-separated integers — arrays $a$ , $b$ , $k$ , $p$ . The first line has array $a$ , the second line has array $b$ , the third line has array $k$ and the fourth one has array $p$ .
It is guaranteed that elements of arrays $a$ and $b$ are positive and do not exceed $10^{4}$ $(1<=a_{i},b_{i}<=10^{4})$ , elements of array $k$ do not exceed $10^{4}$ in the absolute value $(|k|<=10^{4})$ and $p$ is a permutation of numbers from $1$ to $n$ .
Each of the next four lines contains $n$ space-separated integers — arrays $a$ , $b$ , $k$ , $p$ . The first line has array $a$ , the second line has array $b$ , the third line has array $k$ and the fourth one has array $p$ .
It is guaranteed that elements of arrays $a$ and $b$ are positive and do not exceed $10^{4}$ $(1<=a_{i},b_{i}<=10^{4})$ , elements of array $k$ do not exceed $10^{4}$ in the absolute value $(|k|<=10^{4})$ and $p$ is a permutation of numbers from $1$ to $n$ .
输出格式
On a single line print number $s$ — the maximum number of points that a player can win in John's game.
Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.
Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.
输入输出样例
输入 #1
3 2 1 7 7 7 8 8 8 1 2 3 1 3 2
输出 #1
96
输入 #2
2 1 0 1 1 1 1 1 -1 1 2
输出 #2
0
说明/提示
In the first sample you should first apply the operation of the first type, then the operation of the second type.