|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|2 초||512 MB||7||6||5||83.333%|
Birds are stupendous animals. Many species of them perform different rituals throughout their life; from courtship dances of peacocks to moonwalking of red-capped manakins. Among all, we are studying the permutation dance in this problem. This ritual is performed by a group of birds sitting in a row on a wire or tree branch, as shown in the figure.
The ritual can be simplified to a performance based on a sequence of actions of these types:
Given the initial position of the birds in the row and the sequence of actions, your task is to compute the final position of the birds in the ritual.
The input starts with a line containing two space-separated integers n (1 ⩽ n ⩽ 1000) and s (1 ⩽ s ⩽ 5000). The second line contains n space-separated bird names, as the initial configuration of the ritual (positioning of the birds in the row, from left to right). Each bird name is a non-empty string of at most 10 (lowercase) alphanumeric characters (
The sequence of actions is provided in the next s lines, one action per line. Each line is in one of the following formats based on the action type. The
bird-name parameter in the actions has the similar format as the second line of the input.
insert bird-name position
position parameter is an integer showing the number of birds to the left of the insertion position. This parameter is in the range [0, M] where M is the total number of birds in the row before the insertion. Position 0 puts the bird in the beginning (leftmost position) of the row, and position M puts the bird in the end (rightmost position).
relocate bird-name displacement
displacement parameter is an integer that can be positive, negative, or zero. The bird flies to her own position if the displacement is 0. Otherwise, the bird flies over k birds on his right (left) if displacement is positive (negative), where k is the absolute value of displacement. This parameter is in the range [−L, +R] where L and R are respectively the numbers of birds to the left and to the right of the moving bird in the row before the relocation. Displacement −L puts the bird in the beginning (leftmost position) of the row, and displacement+R puts the bird in the end (rightmost position).
No two participating birds share the same name. Moreover, it is guaranteed that all the actions are meaningful at the moment of execution and there is always at least one bird on the branch throughout the ritual.
Print a single line in the output containing the final configuration of the ritual. The line should contain the space-separated list of the bird names in the row (from left to the right).
3 1 juju ashi mashi insert fifi 1
juju fifi ashi mashi
3 15 m1 m2 f insert m3 0 relocate m2 -2 relocate m1 -2 relocate m3 -2 relocate m2 -2 relocate m1 -2 relocate m3 -2 depart m2 relocate m1 1 relocate f 0 relocate m3 0 relocate f -1 relocate m3 -1 relocate m1 -2 relocate f -1
m1 f m3
4 5 hedwig hermes fawkes errol insert pigwidgeon 1 relocate hermes 2 depart fawkes insert buckbeak 0 depart hedwig
buckbeak pigwidgeon errol hermes
A video of the first two sample inputs is provided in the attachment package. Copyright notice: the images and videos of this problem are taken from the following addresses: