Exit Allocation in a Circular Park

There are n people taking a walk in a park which is structured as a circular ring of total length L meters. The park has m exits. For convenience, the people are numbered from 1 to n and the exits are numbered in counter‐clockwise order from 1 to m.

Exit 1 is located at position 0. For every exit with index i (2 ≤ i ≤ m), its position is given as \(a_i\) (in meters) in the counter‐clockwise direction from exit 1. The values \(a_i\) are strictly increasing so that exits \(i\) and \(i+1\) are adjacent (with exit \(m\) adjacent to exit 1 by the circular property). Each exit has a capacity limit \(l_i\) which means at most \(l_i\) people can leave the park via that exit.

Each person starts at a certain position and walks in a given direction (either clockwise or counter‐clockwise) at a constant speed of 1 meter per unit time. When a person reaches an exit that still has remaining capacity, they will immediately leave the park via that exit. In case two or more people arrive at the same exit at exactly the same time while the exit can only allow fewer people than arrived, the person with the smaller index gets to exit, and the others continue walking.

If person i eventually leaves the park via exit \(k_i\) (or \(k_i = 0\) if they never leave), you are required to output the cumulative result computed as

[ (1 \times k_1) ; \text{xor} ; (2 \times k_2) ; \text{xor} ; \cdots ; \text{xor} ; (n \times k_n), ]

where \(\text{xor}\) denotes the bitwise XOR operation.

inputFormat

The input starts with a line containing three integers n, m and L (n is the number of people, m is the number of exits, and L is the length of the park).

The second line contains m-1 integers: \(a_2, a_3, \dots, a_m\), representing the positions of exits 2 to m (exit 1 is at position 0). It is guaranteed that \(0 < a_2 < a_3 < \dots < a_m < L\).

The third line contains m integers: \(l_1, l_2, \dots, l_m\), where \(l_i\) is the capacity of exit i.

Then follow n lines, each describing a person. Each line contains an integer p (the starting position, \(0 \le p < L\)) and a character d which is either 'A' (meaning counter‐clockwise) or 'C' (meaning clockwise), separated by space.

outputFormat

Output a single integer — the resulting XOR value of \((i \times k_i)\) for \(i = 1, 2, \dots, n\). Note that if a person never leaves the park, their \(k_i\) is considered to be 0.

sample

3 3 10
3 7
1 1 1
2 A
3 C
8 A

4