CF193B 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.

The first line contains space-separated integers $ n $ , $ u $ and $ r $ ( $ 1

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.

In the first sample you should first apply the operation of the first type, then the operation of the second type.