Memory Layout of Structs and Basic Types

This problem requires you to simulate a simple memory model for a language that supports four basic types: \(\texttt{byte}\), \(\texttt{short}\), \(\texttt{int}\) and \(\texttt{long}\), with sizes \(1\), \(2\), \(4\) and \(8\) bytes respectively. In addition, user‐defined structure types can be declared. A structure type declaration provides a type name along with an ordered list of members. Each member has a type (either a basic type or a previously defined structure type) and a name. Note that declaring a structure type does not allocate any memory.

An element is defined by specifying its type and name. Elements are allocated in memory sequentially starting at address \(0\), subject to alignment rules. The memory layout rules are as follows:

• Within an element, the members appear in the order defined in the structure. If a member is a structure type, its members are laid out recursively.
• Each element (and every member within a structure) must start at an address which is an integer multiple of its alignment requirement.
• The alignment requirement for a basic type equals its size (e.g. an \(\texttt{int}\) is 4-byte aligned). For a structure type, the alignment requirement equals the maximum alignment requirement among all of its members.
• When laying out a structure, each member is placed at the smallest offset that satisfies the alignment requirement. After all members, padding is added if necessary so that the total size is a multiple of the structure's alignment.

For example, consider the following C++ style code:

struct d {
    short a;
    int b;
    short c;
};
d e;

The structure type d has members with offsets: a at bytes \(0\sim1\), b at \(4\sim7\) (due to 4-byte alignment), and c at \(8\sim9\). After adding padding to satisfy the alignment (4 bytes), the total size of d becomes \(12\) bytes and its alignment is \(4\) bytes.

You are to process \(n\) operations. Each operation is one of the following four types:

1. Define a structure type: You are given a positive integer \(k\), a string \(s\) (the structure type name) and then \(k\) pairs \(t_1, n_1, \dots, t_k, n_k\). The \(i\)th member has type \(t_i\) and name \(n_i\). Output the size and alignment requirement of this structure type separated by a space, in \(\LaTeX\) format when referring to formulas.
2. Define an element: You are given two strings \(t\) and \(n\) representing the type and name of the element. The element is allocated in memory (after all previously defined elements) starting from address \(0\) and must satisfy the alignment requirement of its type. Output the starting address of this newly defined element.
3. Access an element: You are given a dotted access string (e.g. a.b.c). The first token is an element name defined in operation 2 and subsequent tokens refer to members (which can be nested). Output the starting memory address of the innermost member.
4. Access a memory address: You are given a non-negative integer \(\texttt{addr}\). Check if there exists a basic type component whose allocated memory starts exactly at that address. If so, output its access string in the same format as in operation 3; otherwise, output ERR.

Input Format:

The first line contains an integer \(n\), the number of operations.
Each of the next \(n\) lines describes an operation in one of the following formats:
Operation 1 (structure definition):
1 k s t1 n1 t2 n2 ... tk nk
Operation 2 (element definition):
2 t n
Operation 3 (element access):
3 a.b.c
Operation 4 (memory address access):
4 addr

</p>

Output Format:

For each operation that requires an output, print the result on a new line.

The use of \(\LaTeX\) should be applied when referencing formulas such as the sizes and alignment adjustments.

inputFormat

The first line contains an integer \(n\) representing the number of operations. Each of the following \(n\) lines contains an operation as described above.

outputFormat

For each operation that requires an output, print the result in a new line. For structure definitions, output the size and alignment separated by a space. For element definitions, output the starting address. For element and memory accesses, output the starting address or access string, or ERR if the memory address does not correspond to any basic type element.

sample

11
1 3 d short a int b short c
2 d e
3 e.a
3 e.b
3 e.c
4 0
4 4
4 8
4 2
2 int x
3 x

12 4
0
0
4
8
e.a
e.b
e.c
ERR
12
12

</p>