Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], skipTags: ["script","noscript","style","textarea","code"], processEscapes: true }});

Problem J
  String Puzzle
  

  Amazing Coding Magazine is popular among young programmers for its puzzle solving contests offering catchy digital gadgets as the prizes. The magazine for programmers naturally encourages the readers to solve the puzzles by writing programs. Let's give it a try!

  The puzzle in the latest issue is on deciding some of the letters in a string (the secret string, in what follows) based on a variety of hints. The figure below depicts an example of the given hints.
  

  The first hint is the number of letters in the secret string. In the example of the figure above, it is nine, and the nine boxes correspond to nine letters. The letter positions (boxes) are numbered starting from 1, from the left to the right.

  The hints of the next kind simply tell the letters in the secret string at some specic positions. In the example, the hints tell that the letters in the 3rd, 4th, 7th, and 9th boxes are C, I, C, and PIP.

  Note that, not necessarily all of the identical substring pairs in the secret string are given in the hints; some identical substring pairs may not be mentioned.

  Note also that two extents of a pair may overlap each other. In the example, the two-letter substring in boxes 2 and 3 is told to be identical to one in boxes 1 and 2, and these two extents share the box 2.

  In this example, you can decide letters at all the positions of the secret string, which are "CCCIPCCIP". In general, the hints may not be enough to decide all the letters in the secret string.

  The answer of the puzzle should be letters at the specified positions of the secret string. When the letter at the position specified cannot be decided with the given hints, the symbol ? should be answered.

Input

  The input consists of a single test case in the following format.

$n$ $a$ $b$ $q$
$x_1$ $c_1$
...
$x_a$ $c_a$
$y_1$ $h_1$
...
$y_b$ $h_b$
$z_1$
...
$z_q$

  The first line contains four integers $n$, $a$, $b$, and $q$. $n$ ($1 \leq n \leq 10^9$) is the length of the secret string, $a$ ($0 \leq a \leq 1000$) is the number of the hints on letters in specified positions, $b$ ($0 \leq b \leq 1000$) is the number of the hints on duplicated substrings, and $q$ ($1 \leq q \leq 1000$) is the number of positions asked.

  The $i$-th line of the following a lines contains an integer $x_i$ and an uppercase letter $c_i$ meaning that the letter at the position $x_i$ of the secret string is $c_i$. These hints are ordered in their positions, i.e., $1 \leq x_1 ? otherwise.

Sample Input 1

9 4 5 4
3 C
4 I
7 C
9 P
2 1
4 0
6 2
7 0
8 4
8
1
9
6

Sample Output 1

ICPC

Sample Input 2

1000000000 1 1 2
20171217 A
3 1
42
987654321

Sample Output 2

?A



Sample input:
9 4 5 4
3 C
4 I
7 C
9 P
2 1
4 0
6 2
7 0
8 4
8
1
9
6


Sample output:
ICPC

Submission status: Wrong Answer

Solution code:
from bisect import bisect
n, a, b, q = map(int, input().split())

W = [input().split() for i in range(a)]
X = [int(x) for x, c in W]
C = [c for x, c in W]

P = [list(map(int, input().split())) for i in range(b)]
Y = [y for y, h in P] + [n+1]
D = [0]*b

for i in range(b):
    y0, h = P[i]
    y1 = Y[i+1]
    l = y1 - y0
    if y0 < h + l:
        D[i] = y0 - h
    else:
        D[i] = l

Z = [int(input()) for i in range(q)]

idx = 0
S = {}
for i in range(a):
    x = X[i]; c = C[i]
    S[x] = c
    if x < Y[0]:
        continue
    while Y[idx+1] < x: idx += 1
    i = idx
    while Y[0] <= x:
        while x < Y[i]: i -= 1
        y0, h = P[i]; y1 = Y[i+1]
        if h == 0: break
        x = h + ((x - y0) % D[i])
        S[x] = c
ans = []
for z in Z:
    if z not in S:
        i = bisect(Y, z)-1
        while Y[0] <= z:
            while z < Y[i]: i -= 1
            y0, h = P[i]; y1 = Y[i+1]
            if h == 0: break
            z = h + ((z - y0) % D[i])
            if z in S:
                break
    if z in S:
        ans.append(S[z])
    else:
        ans.append('?')
print(*ans, sep='')

Submission status: Wrong Answer

Solution code:
from bisect import bisect
n, a, b, q = map(int, input().split())

W = [input().split() for i in range(a)]
X = [int(x) for x, c in W]
C = [c for x, c in W]

P = [list(map(int, input().split())) for i in range(b)]
Y = [y for y, h in P] + [n+1]
D = [0]*b

for i in range(b):
    y0, h = P[i]; y1 = Y[i+1]
    l = y1 - y0
    D[i] = min(y0 - h, l)

Z = [int(input()) for i in range(q)]

idx = 0
S = {}
for i in range(a):
    x = X[i]; c = C[i]
    S[x] = c
    if x < Y[0]:
        continue
    while Y[idx+1] < x: idx += 1
    i = idx
    while Y[0] <= x:
        while x < Y[i]: i -= 1
        y0, h = P[i]; y1 = Y[i+1]
        if h == 0: break
        x = h + ((x - y0) % D[i])
        assert x < y0
        S[x] = c
def check(z):
    if z in S:
        return S[z]
    i = bisect(Y, z)-1
    while Y[0] <= z:
        while z < Y[i]: i -= 1
        y0, h = P[i]; y1 = Y[i+1]
        if h == 0: break
        z = h + ((z - y0) % D[i])
        assert z < y0
        if z in S:
            return S[z]
    return '?'
print(*map(check, Z), sep='')

Submission status: Accepted

Solution code:
from bisect import bisect
n, a, b, q = map(int, input().split())

W = [input().split() for i in range(a)]
X = [int(x) for x, c in W]
C = [c for x, c in W]

P = [list(map(int, input().split())) for i in range(b)]
Y = [y for y, h in P] + [n+1]
D = [0]*b

for i in range(b):
    y0, h = P[i]; y1 = Y[i+1]
    l = y1 - y0
    D[i] = min(y0 - h, l)

idx = 0
S = {}
for i in range(a):
    x = X[i]; c = C[i]
    S[x] = c
    if x < Y[0]:
        continue
    while Y[idx+1] <= x: idx += 1
    i = idx; j = i
    while Y[0] <= x:
        while x < Y[i]: i -= 1
        y0, h = P[i]; y1 = Y[i+1]
        if h == 0: break
        x = h + ((x - y0) % D[i])
        assert x < y0
        S[x] = c
def check(z):
    if z in S:
        return S[z]
    i = bisect(Y, z)-1
    while Y[0] <= z:
        while z < Y[i]: i -= 1
        y0, h = P[i]; y1 = Y[i+1]
        if h == 0: break
        z = h + ((z - y0) % D[i])
        assert z < y0
        if z in S:
            return S[z]
    return '?'

Z = [int(input()) for i in range(q)]
print(*map(check, Z), sep='')

Submission status: Accepted

Solution code:
from bisect import bisect
n, a, b, q = map(int, input().split())

W = [input().split() for i in range(a)]
X = [int(x) for x, c in W]
C = [c for x, c in W]

P = [list(map(int, input().split())) for i in range(b)]
Y = [y for y, h in P] + [n+1]
D = [0]*b

for i in range(b):
    y0, h = P[i]; y1 = Y[i+1]
    D[i] = min(y0 - h, y1 - y0)

idx = 0
S = {}
for i in range(a):
    x = X[i]; c = C[i]
    S[x] = c
    if x < Y[0]:
        continue
    while Y[idx+1] <= x: idx += 1
    i = idx
    while Y[0] <= x:
        while x < Y[i]: i -= 1
        y0, h = P[i]
        if h == 0: break
        x = h + ((x - y0) % D[i])
        S[x] = c
def check(z):
    if z in S:
        return S[z]
    i = bisect(Y, z)-1
    while Y[0] <= z:
        while z < Y[i]: i -= 1
        y0, h = P[i]
        if h == 0: break
        z = h + ((z - y0) % D[i])
        if z in S:
            return S[z]
    return '?'

Z = (int(input()) for i in range(q))
print(*map(check, Z), sep='')

Submission status: Runtime Error

Solution code:
from bisect import bisect
n, a, b, q = map(int, input().split())

W = [input().split() for i in range(a)]
X = [int(x) for x, c in W]
C = [c for x, c in W]

P = [list(map(int, input().split())) for i in range(b)]
Y = [y for y, h in P] + [n+1]
D = [0]*b

for i in range(b):
    y0, h = P[i]
    y1 = Y[i+1]
    l = y1 - y0
    if y0 < h + l:
        D[i] = y0 - h
    else:
        D[i] = l

Z = [int(input()) for i in range(q)]

idx = 0
S = {}
for i in range(a):
    x = X[i]; c = C[i]
    S[x] = c
    while Y[idx+1] < x: idx += 1
    i = idx
    while Y[0] <= x:
        while x < Y[i]: i -= 1
        y0, h = P[i]; y1 = Y[i+1]
        if h == 0: break
        x = h + ((x - y0) % D[i])
        S[x] = c
ans = []
for z in Z:
    if z not in S:
        i = bisect(Y, z)
        while Y[0] <= z:
            while z < Y[i]: i -= 1
            y0, h = P[i]; y1 = Y[i+1]
            if h == 0: break
            z = h + ((z - y0) % D[i])
            if z in S:
                break
    if z in S:
        ans.append(S[z])
    else:
        ans.append('?')
print(*ans, sep='')