Person in Charge

• SleepingCup

Problem Background

In high-level programming languages such as C++, besides basic data types like int and float, we can usually define custom structure types. In this problem, you need to simulate the structure definition mechanism of a C++-like high-level language and calculate relevant memory occupation information.

Problem Description

There are exactly 4 basic data types in this language: byte, short, int, long, which occupy 1, 2, 4 and 8 bytes of memory space respectively.

To define a structure type, you need to specify a type name and its members. Each member is given in order with its type and name. The type can be a basic type or a structure type that has been defined previously. Note that defining a structure type does not create a concrete instance, meaning it occupies no memory space itself.

To define an element, you need to specify its type and name. Elements occupy memory space following these rules:

• All members of an element are arranged in memory in the order they were defined, and the same rule applies to members of structure types.
• To ensure efficient memory access, the address occupation of an element must satisfy the alignment rule: the size of any type and the starting address of an element of that type must be aligned to an integer multiple of the type's alignment requirement. Specifically:
  • For a basic type: its alignment requirement is equal to its memory size. For example, the int type requires 4-byte alignment, and the same logic applies to other basic types.
  • For a structure type: its alignment requirement is equal to the maximum value of the alignment requirements of all its members. For example, a structure type containing an int and a short requires 4-byte alignment.

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

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

This code defines a structure type d and an element e. Element e has three members: e.a, e.b, e.c, which occupy memory addresses $0 \sim 1$, $4 \sim 7$, $8 \sim 9$ respectively. Since the structure type d requires 4-byte alignment, e occupies addresses $0 \sim 11$ with a total size of 12 bytes.

You need to process $n$ operations, each belonging to one of the following four types:

1. Define a structure type: Given a positive integer $k$ and strings $s, t_1, n_1, \dots, t_k, n_k$, where $k$ is the number of members of the structure, $s$ is the type name of the structure, $t_1, t_2, \dots, t_k$ are the types of the members in order, and $n_1, n_2, \dots, n_k$ are the names of the members in order. You need to output the size and alignment requirement of this structure type, separated by a single space.
2. Define an element: Given two strings $t, n$ representing the type and name of the element respectively. All defined elements are arranged sequentially starting from memory address $0$, complying with the address alignment rule. You need to output the starting address of the newly defined element.
3. Access an element: Given a string $s$ representing the element to access. Consistent with languages such as C++, the dot operator . is used to access members of a structure type. For example, a.b.c means that a is a defined element of a structure type with a member named b (also a structure type), which has a member named c. You need to output the starting address of the innermost element being accessed.
4. Access a memory address: Given a non-negative integer $addr$ representing the address to access. You need to determine if there exists an element of a basic type that occupies this address. If yes, output the element in the access format specified in operation 3; otherwise, output ERR.

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

• Let a structure have $k$ members with sizes $s_1,...,s_k$ and alignment requirements $a_1,...,a_k$ respectively.
• The alignment requirement $a$ of this structure is $a=\max\{a_1,...,a_k\}$.
• Let the address offsets of these members in memory arrangement be $o_1,...,o_k$ respectively, then:
  • $o_1 = 0$;
  • For $i=2,...,k$, $o_i$ is the minimum value that satisfies $o_{i-1}+s_{i-1}\le o_i$ and $o_i \bmod a_i = 0$;
  • The size $s$ of this structure is the minimum value that satisfies $o_k+s_k\le s$ and $s \bmod a = 0$.

The formal definition for the memory arrangement of defined elements is as follows:

• Let the $i$-th defined element have size $s_i$, alignment requirement $a_i$, and starting address $b_i$.
• Then $b_1 = 0$, and for $2\le i$, $b_i$ is the minimum value that satisfies $b_{i-1} + s_{i-1}\le b_i$ and $b_i \bmod a_i = 0$.

Input Format

The first line contains a positive integer $n$, representing the number of operations.

The following lines describe each operation in sequence. The first positive integer $op$ of each line denotes the operation type:

• If $op = 1$, first input a string $s$ and a positive integer $k$ (the type name and the number of members). Then input $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 element.
• If $op = 3$, input a string $s$, representing the element to access.
• If $op = 4$, input a non-negative integer $addr$, representing the memory address to access.

Output Format

Output $n$ lines in sequence, each representing the result of the corresponding operation as specified in the problem description.

Samples

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

Sample (1) Explanation

In the structure 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, the size of structure type a is 8 bytes. The size and alignment requirement of structure type b can be calculated similarly, resulting in a size of 16 bytes and an alignment requirement of 8 bytes.

Sample (2)

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

Sample (2) Explanation

In the second operation of type 4, the accessed memory address falls exactly into a memory gap reserved for address alignment, so no element of a basic type occupies this address.

Sample (3)

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

Data Range

For all test data, it is guaranteed that $1 \le n \le 100$, $1 \le k \le 100$, $0 \le addr \le 10^{18}$.

All defined structure type names, member names and element names consist of lowercase letters with no more than 10 characters, and none of them are byte, short, int, long (i.e., no conflict with basic type names).

All defined structure type names and element names are distinct, and member names within the same structure are distinct. However, different structures may have identical member names, and a member name in a structure may be the same as a defined structure type name or element name.

All operations comply with the specifications and requirements of the problem: no undefined types are used in structure definitions, no non-existent elements or members are accessed, etc.

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

Special Properties:

• A: No operations of type 1 exist.
• B: There is exactly one operation of type 1.
• C: All member types given in operations of type 1 are basic types.
• D: The only available basic type is long.