Marksheet versions with defensive copies

Problem

An immutable Marksheet keeps its own private copy of the marks. withMark(i, m) returns a new marksheet with one mark changed, and every older version must keep its old marks. Version 0 is the first marksheet; each UPDATE makes the next version from the latest one. Answer TOTAL v with the total of version v and SHOW v with its marks.

Input, output and limits

Input: The first line has n, the number of subjects; the second line has n marks. Then a line with q, then q lines: UPDATE i m (subject i, from 1), TOTAL v or SHOW v.
Output: One line for every TOTAL (the total) and every SHOW (the marks, separated by single spaces).
Constraints: 1 ≤ n ≤ 50
1 ≤ q ≤ 200
0 ≤ every mark ≤ 100
Every queried version already exists

Examples

Example

Input

3
50 60 70
6
UPDATE 2 90
TOTAL 0
TOTAL 1
UPDATE 1 10
SHOW 1
SHOW 2

Output

Version 1 still shows 50 for subject 1 after version 2 changed it.

Hints

Try the problem first. Open one hint at a time.

Hint 1

Copy the array in the constructor with Arrays.copyOf, so the caller's array is never shared.

Hint 2

withMark copies the marks, changes the copy, and passes it to new Marksheet(...).

Hint 3

Keep a Marksheet[] versions of size q + 1 and the index of the latest version.

Write your Java code, run it on the examples and submit it to hidden tests.

Solve in the editor

All Java problems

Problem

Input, output and limits

Examples

Hints

More References, Casting & Immutability problems

Problem

Input, output and limits

Examples

Hints

More References, Casting & Immutability problems