A shared shopping list

distributed systems replication hash table simulation

A shopping list lives in several copies, one in the phone of each member of a family. Each copy changes the list locally and now and then receives the whole state of another copy. For the copies to converge and lose nothing, the list is built as an OR-set (observed-remove set).

add r x: copy r adds the element x. Each addition gets a new tag, a pair (r, k), where k is the number of this addition among copy r's additions, counting from 1. The copy remembers the pair (x, tag).
remove r x: copy r crosses out x: all tags of the element x that it currently sees become removed. Tags it has not seen yet are left alone.
sync a b: copy b receives the state of copy a: it joins its pairs with a's pairs, and its removed tags with a's removed tags.
show r: show the list of copy r: an element is in the list if it has at least one tag that is not removed.

Carry out the operations and print the answers to all show operations.

Input

The first line holds the number of copies R and the number of operations n (1 ≤ R ≤ 20, 1 ≤ n ≤ 2·10⁴). Then n operations, one per line. Elements are integers from 1 to 10⁹, copy numbers from 1 to R. There are at most 1500 sync operations and at most 300 show operations.

Output

For each show operation, a line with the list's elements in increasing order separated by spaces, or - if the list is empty.

In the first sample the second family member crosses out milk (7), and the first, not yet knowing this, adds milk again. The crossing out touches only the tag the second member saw, so after the exchange milk is in both lists: a concurrent addition wins over a removal. In the second sample the same number 5 was added by two copies, and it can be crossed out completely only once the third copy has seen both tags.

Examples

Example 1

Input

2 10
add 1 7
add 1 9
sync 1 2
remove 2 7
add 1 7
show 2
sync 2 1
sync 1 2
show 1
show 2

Output

9
7 9
7 9

Example 2

Input

3 12
add 1 5
add 2 5
sync 1 3
remove 3 5
show 3
sync 2 3
show 3
remove 3 5
sync 3 1
sync 3 2
show 1
show 2

Output

-
5
-
-

Limits

Time · Python: 8000 ms
Time · Go: 4000 ms
Memory: 256 MB
Judging: 6 tests

Walkthrough

Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.

1Hint 1

Why not keep just a set of elements and a set of removed elements? What happens to the milk of the first sample if “crossed out” means “never again”?

2The idea

What is removed is not the element but the specific additions the remover has seen. So each addition has its own tag, and the state of a copy is two sets: pairs (element, tag) and removed tags. Both only grow, and merging is union; union is commutative, associative and idempotent, so copies that received the same states in any order and any number of times see the same thing. An element is in the list if it has a live tag left. An addition the remover did not know about is not touched by the removal, hence the rule “addition wins”.

3Walkthrough

For each copy keep a set of pairs, a set of removed tags and a counter of its own additions. add puts in a new pair. remove moves all of the element's tags from the copy's pairs into the removed ones. sync is two unions. show lists the elements of pairs whose tags are not among the removed, without repeats, in increasing order.

Removed tags are kept forever, like tombstones in RGA: without them an old pair arriving later would bring the element back to life. Real systems clear such tombstones away over time, once all copies have confirmed they saw them.

3+Solution

4Complexity

add is O(1); remove and show are O(size of the copy's state); sync is O(size of the sender's state). The state grows with the number of additions, which is why the problem limits the number of exchanges and shows.

5Common mistakes

Removing the element rather than the tags. That is how a “two-phase set” works: what was crossed out never comes back. The first sample catches this.
Removing tags you have not seen. If remove crosses an element out in all future states too, a concurrent addition disappears, which is exactly the loss the OR-set protects against.
A tag without the copy number. An addition number on its own is not unique: two copies each have their own “first addition”.

Algorithms behind it

SYS Data structure CRDT Data whose copies are edited independently and merged in any order: counters, sets, text. O(1) per operation for a counter and a set; insertion into text O(1) on average 2 problems DS Data structure Hash table Search, insert and delete by key in O(1) on average: the key turns into the number of an array cell. O(1) on average 2 problems