Background

In high-level languages such as C++, besides basic types like int and float, you can usually define your own struct types. In this problem, you need to simulate a struct definition method similar to that of a C++-like high-level language, and compute the corresponding memory usage and related information.

Problem Description

In this language, there are $4$ basic types: byte, short, int, long, which occupy $1$, $2$, $4$, $8$ bytes of memory, respectively.

When defining a struct type, you need to provide the type name and its members. Each member must be given, in order, with its type and name. A type can be a basic type or a struct type that has been defined earlier. Note that defining a struct type does not define any concrete variable, so it does not occupy memory.

When defining an object (an instance/variable), you need to provide the object’s type and name. Objects occupy memory according to the following rules:

• All members inside an object are laid out in memory in the same order as in the definition. The same applies to members whose type is a struct.
• To ensure efficient memory access, the object’s address allocation must satisfy the alignment rules: for any type, both the size of the type and the starting address of an object of that type in memory must be aligned to an integer multiple of the type’s alignment requirement. Specifically:
  • For basic types: the alignment requirement equals the size it occupies. For example, int must be aligned to $4$ bytes, and similarly for the others.
  • For struct types: the alignment requirement equals the maximum alignment requirement among its members. For example, a struct type containing int and short must be aligned to $4$ bytes.

Here is an example (written in C++ format):

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

This code defines the struct type d and an object e. Object e contains three members e.a, e.b, e.c, occupying address ranges $0 \sim 1$, $4 \sim 7$, and $8 \sim 9$, respectively. Since type d needs to be aligned to $4$ bytes, e occupies addresses $0 \sim 11$, with a total size of $12$ bytes.

You need to process $n$ operations. Each operation is one of the following four types:

1. Define a struct type. Specifically, you are given a positive integer $k$ and strings $s, t_1, n_1, \dots, t_k, n_k$, where $k$ is the number of members, $s$ is the type name, $t_1, t_2, \dots, t_k$ are the member types in order, and $n_1, n_2, \dots, n_k$ are the member names in order. You need to output the size and alignment requirement of this struct type, separated by a space.

2. Define an object. Specifically, you are given strings $t, n$, representing the object’s type and name. All defined objects are placed in order in memory starting from address $0$, and must satisfy the address alignment rules. You need to output the starting address of the newly defined object.

3. Access an object. Specifically, you are given a string $s$ representing the object to be accessed. As in C++ and similar languages, . is used to access members of a struct type. For example, a.b.c means a is a defined object; it is a struct type and has a member named b, which is also a struct type and has a member named c. You need to output the starting address of the innermost element accessed as above.

4. Access a memory address. Specifically, you are given a non-negative integer $addr$, representing the address to access. You need to determine whether there exists a basic-type element that occupies this address. If yes, output that element in the same access format as in operation 3; otherwise output ERR.

Input Format

Line $1$: a positive integer $n$, the number of operations.

The following lines describe the operations in order. The first integer on each line is $op$, the operation type:

• If $op = 1$, first input a string $s$ and a positive integer $k$, representing the type name and number of members. Then follow $k$ lines, each containing two strings $t_i, n_i$, representing the type and name of each member in order.

• If $op = 2$, input two strings $t, n$, representing the type and name of the object.

• If $op = 3$, input one string $s$, representing the object to be accessed.

• If $op = 4$, input one non-negative integer $addr$, representing the address to be accessed.

Output Format

Output $n$ lines, in order, each being the result of the corresponding operation, as required in the statement.

5
1 a 2
short aa
int ab
1 b 2
a ba
long bb
2 b x
3 x.ba.ab
4 10

8 4
16 8
0
4
x.bb

Hint

Sample 1 Explanation

In struct type a, the short member aa occupies addresses $0 \sim 1$, and the int member ab occupies addresses $4 \sim 7$. Since its alignment requirement is $4$ bytes, its size is $8$ bytes. Similarly, the size of struct type b is $16$ bytes, and its alignment requirement is $8$ bytes.

Sample 2

See struct/struct2.in and struct/struct2.ans in the contestant directory.

Sample 2 Explanation

In the second operation 4, the accessed memory address lies exactly in a “hole” left for address alignment, so no basic-type element occupies it.

Sample 3

See struct/struct3.in and struct/struct3.ans in the contestant directory.

Constraints

For all data, $1 \le n \le 100$, $1 \le k \le 100$, $0 \le addr \le 10^{18}$.

All defined struct type names, member names, and object names consist of at most $10$ lowercase letters, and none of them is byte,short,int,long (i.e., they do not share a name with any basic type).

All defined struct type names and object names are pairwise distinct, and member names within the same struct are pairwise distinct. However, different structs may have the same member name, and a member name within some struct may also be the same as a defined struct or object name.

It is guaranteed that all operations follow the rules and requirements described in the statement. In particular, struct definitions will not include nonexistent types, and accesses will not refer to nonexistent objects or members.

It is guaranteed that the size of any struct and the maximum memory address occupied by defined objects do not exceed $10^{18}$.

Special property A: there is no operation $1$.

Special property B: there is only one operation $1$.

Special property C: in all operations $1$, all member types are basic types.

Special property D: the only basic type is long.

Hint

The formal definitions of the alignment requirement and size of a struct type are as follows:

• Suppose the struct has $k$ members, with sizes $s_1,...,s_k$ and alignment requirements $a_1,...,a_k$.
• Then the alignment requirement of this struct is $a=\max\{a_1,...,a_k\}$.
• Let the address offsets of these members in the layout be $o_1,...,o_k$. Then:
  • $o_1 = 0$.
  • For $i=2,...,k$, $o_i$ is the smallest value such that $o_{i-1}+s_{i-1}\le o_i$ and $a_i$ divides $o_i$.
  • The size $s$ of this struct is the smallest value such that $o_k+s_k\le s$ and $a$ divides $s$.

The formal definition of the memory layout when defining objects is as follows:

• Suppose the $i$-th defined object has size $s_i$, alignment requirement $a_i$, and starting address $b_i$.
• Then $b_1 = 0$. For $2\le i$, $b_i$ is the smallest value such that $b_{i-1} + s_{i-1}\le b_i$ and $a_i$ divides $b_i$.

Translated by ChatGPT 5