Mapmaker

Interview

Time limit1sMemory limit128 MB

Summary

Given array declarations with bounds and element sizes, compute each reference's physical address with the row-major address formula.

Level: Medium4 of 10
Topics: Array, Math, Implementation, Simulation
Solved: No attempts yet

Problem

The Cybersoft Computer Company (a leader in programming languages) has hired you to work on a new programming language named A--. Your job is the array-mapping part of the language: given an array reference such as x[5, 6], you must map it to an actual physical address. To do this, write a program that reads several array declarations and references and prints the physical address of each reference. Every physical address must be printed as a base-10 integer.

The physical address of an array reference $A[i_1, i_2, \ldots, i_D]$ is given by

$C_0 + C_1 i_1 + C_2 i_2 + \cdots + C_D i_D,$

where the constants $C_0, \ldots, C_D$ are defined as follows:

$B$ = base address of the array
$D$ = number of dimensions of the array
$L_d$ = lower bound of dimension $d$
$U_d$ = upper bound of dimension $d$
$C_D$ = size of one array element, in bytes
$C_d = C_{d+1}\,(U_{d+1} - L_{d+1} + 1)$ for $1 \le d < D$
$C_0 = B - C_1 L_1 - C_2 L_2 - \cdots - C_D L_D$

Input

The first line contains two positive integers $N$ and $R$ : $N$ is the number of arrays that are declared, and $R$ is the number of array references whose addresses must be computed. The next $N$ lines each declare one array, and the following $R$ lines each contain one array reference.

Each array-declaration line contains, in order: the array name (at most 10 characters), a positive integer giving the base address of the array, a positive integer giving the size in bytes of each array element, and $D$ , the number of dimensions ( $1 \le D \le 10$ ). These are followed, on the same line, by $D$ pairs of integers giving the lower and upper bounds of dimensions $1, \ldots, D$ , respectively.

Each array-reference line contains the array name followed by the integer indices $i_1, i_2, \ldots, i_D$ , where $D$ is the number of dimensions of that array.

Output

For each reference, print one line containing the reference together with its physical address, formatted exactly as follows:

Print the array name.
Print a left square bracket [.
Print the index values, separating each consecutive pair of indices by a comma and a single space.
Print a right square bracket, a space, an equals sign, and another space (] = ).
Print the physical address.

Examples2

Example 1

Input

3 4
ONE    1500 2 2 0 3 1 5
TWO    2000 4 3 1 4 0 5 5 10
THREE  3000 1 1 1 9
ONE    2 4
THREE  7
TWO    2 0 6
TWO    3 3 9

Expected output

ONE[2, 4] = 1526
THREE[7] = 3006
TWO[2, 0, 6] = 2148
TWO[3, 3, 9] = 2376

Example 2
Input
```
1 1
A 100 4 1 0 9
A 5
```
Expected output
```
A[5] = 120
```