TLE '17 Contest 5 P4 - Cloning

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 1.0s
Java 1.5s
Python 3.0s
Memory limit: 256M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
Dankey Kang and his horde of clones.

Dankey Kang, Croneria's most fearsome villain, has decided to increase the size of his gang by creating many clone soldiers. Each clone can be one of two types, type 0 or type 1.

There are two possible methods of cloning, which can be described as a string of clone types S and T. That is, S and T are strings only containing 0 and 1.

Initially, there is one clone of type 0 in the line. Then, the following process will continue indefinitely:

  • The first clone in the line will leave the front of the line to fight.
  • If that clone's type is 0, a string of clones matching S will be added to the end of the line, in order.
  • If that clone's type is 1, a string of clones matching T will be added to the end of the line, in order.

Dankey Kang is then interested in Q of the clones. In particular, he wants to know the type of the a_i^{th} clone that leaves the line, indexed starting at 1.

Constraints

For all subtasks:

2 \le |S|,|T| \le 10^5

1 \le Q \le 10^5

1 \le a_i \le 10^{12}

Subtask Points Additional Constraints
1 5 |S|,|T|,Q,a_i \le 20
2 15 a_i \le 10^6
3 20 |S|=|T|
4 25 |S|,|T| \le 10
5 25 |S|,|T| \ge 5\,000
6 10 No additional constraints.

Input Specification

The first line will contain string S.

The second line will contain string T.

The third line will contain the integer Q.

On the next Q lines, the i^{th} line will contain integer a_i.

Output Specification

Output Q lines. The i^{th} line of output will contain the type of the {a_i}^{th} clone that leaves the line.

Sample Input

100
10
9
1
2
3
4
5
6
7
8
9

Sample Output

0
1
0
0
1
0
1
0
0

Comments

There are no comments at the moment.