Blocks Cut From the Back

You are given the head of a singly linked list of n nodes and a non-empty list sizes of positive integers. Cut the chain into blocks measured from the back: the last block has sizes[0] nodes, the block before it sizes[1] nodes, and so on, starting again at sizes[0] after the end of sizes. Keep going towards the front as long as the next full block fits; the nodes left over at the very front (if any) form one more, shorter block. Number the blocks from the back, starting at 1 for the last block.

Reverse the order of the nodes inside every even-numbered block (the leftover front block included, if its number is even), leave the other blocks unchanged, and return the new head. Re-link the existing nodes; do not create new ones.

Examples

Input:  head = 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10, sizes = [2, 3]
Output: 3 -> 2 -> 1 -> 4 -> 5 -> 8 -> 7 -> 6 -> 9 -> 10
Explanation: from the back: [9, 10] #1, [6, 7, 8] #2, [4, 5] #3, [1, 2, 3] #4.

Input:  head = 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9, sizes = [2]
Output: 1 -> 3 -> 2 -> 4 -> 5 -> 7 -> 6 -> 8 -> 9
Explanation: [8, 9] #1, [6, 7] #2, [4, 5] #3, [2, 3] #4, and the leftover [1] is block #5.

Constraints

• 0 <= number of nodes <= 5 * 10**4
• 1 <= len(sizes) <= 100 and 1 <= sizes[i] <= 10**5
• Target: O(n + number of blocks) time. Walking from the head again for every block is too slow for the large tests.

Goals

• Turn block boundaries defined from the tail into a plan that runs from the head
• Get the parity of each block's number right, including a short front block
• Reverse the chosen blocks in place in one forward pass