A counter going both ways

amortized bit tricks simulation

A counter holds a number of k bits and supports two operations: + adds one, - subtracts one. Counting goes round in a circle: after 2^k − 1 comes 0, and before 0 comes 2^k − 1. Every bit that changes during an operation is a flip: for example, going from 0111 to 1000 flips all four bits.

The counter starts at the number v and performs a sequence of operations. How many bit flips will there be in total, and what was the largest number of flips in one operation?

Input

The first line holds k, v and n (1 ≤ k ≤ 62, 0 ≤ v < 2^k, 1 ≤ n ≤ 10⁶). The second is a string of n characters + and -.

Output

Two numbers: the total number of flips and the largest number of flips in one operation.

Examples

Example 1

Input

4 0 8
++++++++

Output

15 4

Limits

Time · Python: 2500 ms
Time · Go: 1000 ms
Memory: 256 MB
Judging: 10 tests

Walkthrough

Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.

1Hint 1

Which bits flipped going from v to w? Exactly those in which v and w differ.

2The idea

The number of differing bits is the number of ones in v XOR w. The new value takes one operation: (v ± 1) cut down to k bits by the mask 2^k − 1, and the mask also handles going over the edge of the circle. The ones in a number are counted by a built-in function: int.bit_count() in Python, bits.OnesCount64 in Go. Every operation is O(1), however many bits it flips.

3Walkthrough

The natural solution is to flip the bits one at a time, as in column addition: an increment erases the tail of ones and sets one one, a decrement erases the tail of zeros and sets one zero. While the operations only add, this is fast: the article on amortized analysis proves that n increments from zero flip fewer than 2n bits. But the proof relies on coins lying on the ones, and decrementing spends them in the wrong direction. A counter standing at 2⁶¹ − 1 and doing +-+-… flips all 62 bits every time: 0111…1 ↔ 1000…0. This is the fourth test: a million operations, 62 million flips, and a bit-by-bit solution in Python does not make it.

The answer can be large, up to 62·10⁶, but it fits in a 64-bit integer.

The sample has 8 increments from zero: 1, 2, 1, 3, 1, 2, 1 and 4 flips, 15 in total, less than 2 · 8. For increments in a row there is a formula too: from 0 to n bit number j flips ⌊n/2^j⌋ times, and the sum over all bits is 2n minus the number of ones in the notation of n.

3+Solution

4Complexity

O(n): each operation is a few actions on a 64-bit number.

5Common mistakes

Flipping one bit at a time. Correct, but alternating at the boundary takes 62 steps per operation.
Forgetting the circle. Adding one to 2^k − 1 flips all k bits and gives 0; subtracting one from 0 also flips k bits. Without the mask you get a number of k + 1 bits or a negative one.
Negative numbers in Python. (0 − 1) & mask gives 2^k − 1, as it should; without the mask bit_count counts the ones in −1, that is, one.

Algorithms behind it

TEC Technique Amortized analysis A bound on a whole sequence of operations, not on each one: by a sum, by coins and by a potential, and where it does not help. a bound on a sequence 2 problems TEC Technique Bit tricks A number as a set of flags: masks, the lowest set bit, counting ones and going through subsets without recursion. O(1) per operation on a word 1 problem