Indian National Olympiad in Informatics

Related:

Online Programming Contest, 2-3 October 2004

IARCS home > OLYMPIAD

Basic Division

Problem 2: A Board Game, (K Narayan Kumar, CMI)

In this task you have to determine the outcome of a board game. The board on which the game is played has N places labelled 1,2,...,N. Each position is marked with either a + or a -. The position 1 is always marked with a +.

A token is initially placed at position 1. The game proceeds as follows: In each round, a single die is thrown. Let the current position of the token be j and let the die show d. The new position of the token is determined as follows:

If the position j is labelled + and if j+d ≤ N then the token moves to j+d, otherwise it remains at j.
If the position j is labelled - and if j-d ≥ 1 then the token moves to j-d, otherwise it remains at j

The score at the end of the game is the number of times the token visits the position 1.

For example if the board looks like

  1   2   3   4   5   6   7   8   9   10  11  12
  +   +   -   +   -   -   +   -   -   +   -   -

and the sequence of throws of the die is 1,1,2,3,2,6,3,2,6,2 then the sequence of positions visited by the token is 1 2 3 1 4 6 6 3 1 7 9 and the resulting score is 3.

You are given the description of the board and a sequence of throws of the die. Your aim is to determine the score at the end of the game.

Input format

The first line contains two integers N and M where N is the number of positions on the board and M is the number of throws of the die. Lines 2,...,N+1 contain a + or a -. Line i+1, 1 ≤ i ≤ N, indicates whether position i is marked with a + or a -. The next M lines, lines N+2,..., N+1+M, each contain a single integer d indicating a throw of the die, with 1 ≤ d ≤ 6.

Output format

A single integer indicating the score.

Test Data

You may assume 7 ≤ N ≤ 10000 and 1 ≤ M ≤ 10000.

Example

We now illustrate the input and output formats using the example described above.

Sample input:

12  10
+
+
-
+
-
-
+
-
-
+
-
- 
1
1
2
3
2
6
3
2
6
2

Sample output:

Test data:

10 zipped test inputs and outputs