Bee Observation (APCS 2024-01 Intermediate)

Bob the bee is in an \(m \times n\) honeycomb. Every cell contains an uppercase or lowercase English letter.

Bob starts at the bottom-left cell. With rows listed from top to bottom and columns from left to right in the input, the six movement directions are:

Process the moves in order. If a move would take Bob outside the honeycomb, Bob stays in the same cell, but that step is still considered completed.

Output the string formed by the letter in Bob's cell after every step, followed by the number of distinct characters in that string. Uppercase and lowercase letters are considered different characters.

Input

The first line contains three integers \(m\), \(n\), and \(k\): the number of rows, the number of columns, and the number of moves.

The next \(m\) lines each contain a string of length \(n\), describing the rows of the honeycomb from top to bottom.

The last line contains \(k\) integers \(d_1,d_2,\ldots,d_k\), the movement directions in order.

Constraints

• \(1 \le m,n \le 20\)
• \(1 \le k \le 100\)
• Every honeycomb character is an uppercase or lowercase English letter.
• \(0 \le d_i \le 5\)

Output

Output two lines:

• On the first line, output a string of length \(k\) containing the letter in Bob's cell after each step.
• On the second line, output the number of distinct characters in the first-line string.

Scoring

There are two subtasks:

Sample Input 1

2 4 5
TyuI
ABaB
0 1 2 3 0

Sample Output 1

Tyaau
4

Sample Explanation 1

S marks the starting cell, and each number marks the cell occupied by Bob after that step. A × means that the move hits a wall and Bob stays in place.

Sample Input 2

4 6 11
rMmnis
LRveEX
ZexDoc
HAdbHA
0 1 5 1 1 0 3 0 0 1 0

Sample Output 2

ZeLRvmvmmnn
7

Sample Explanation 2

On steps \(9\) and \(11\), Bob hits the upper wall and therefore stays on m and n, respectively.

Source

APCS Programming Practice, January 2024, Problem 2: ZeroJudge m932, "Bee Observation".