In the official editorial, each transition is done in \(O(K)\) time. We will show a solution with \(O(1)\) transition with bit operations. In this problem, as \(0 \le P \le 5\) , it can be represented in \(3\) bits. We will use \(4\) bits with an additinal \(1\) bit as an identifier. You may think an addition of states can be done by integer addition, if we can ignore carrying. We need to implement minP(x) function, which calculates \(\mathrm{min}(P, *)\) for each \(4\) digits of \(x\). Define variables:

• mask : Repeats 0111
• mmm : Repeats 1000
• ppp : Repeats an expression of \(P\) in hexadecimal

Actually minP(x) can be implemented by x - ((((mmm + x - ppp) & mmm) * 7 >> 3) & (mmm + x - ppp)). To see this, see that (mmm + x - ppp) & mmm has a bit if and only if each of \(4\)-digit number is equal to or greater than \(P\).

AC Code （PyPy3）