У Джона Доу есть четыре массива a, b, k и p. Каждый из них состоит из n целых чисел. Элементы всех массивов индексируются начиная c 1. Массив p является перестановкой целых чисел от 1 до n.
Джон придумал игру для себя и своих друзей. Изначально игроку предлагается массив a. Игрок должен последовательно выполнить ровно u операций над a. Разрешается выполнять следующие операции:
- Операция 1: Для каждого
изменить ai на 
. Выражение 
обозначает применение операции побитового исключающего или к числам x и y. Данная операция есть во всех современных языках программирования, например, в языке C++ и Java она обозначается «^», в Pascal — «xor». - Операция 2: Для каждого изменить ai на api + r. При выполнении этой операции все изменения происходят одновременно.
После применения всех u операций, количество очков, которые получает игрок, определяется по формуле 
.
Джон хочет узнать какое максимальное количество очков можно набрать в его игре. Помогите ему.
Выходные данные
Выведите в единственной строке число s — максимальное количество очков, которое можно получить в игре Джона.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.
Примечание
В первом примере нужно применить сначала операцию первого типа, а затем операцию второго типа.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2 1
7 7 7
8 8 8
1 2 3
1 3 2
|
96
|
|
2
|
2 1 0
1 1
1 1
1 -1
1 2
|
0
|