Syncing two replicas

hashing tree distributed systems prefix sums

Two replicas of a database each store n blocks, and it has to be found out over the network which blocks have diverged. Sending all the blocks is expensive, so both sides build the same Merkle tree over them and compare hashes from the top down. The tree is built as in RFC 6962: if a range has more than one block, the left subtree takes the largest power of two less than the length of the range, and the right one the rest.

Reconciliation starts with the roots. If the hashes of the nodes match, nobody goes inside: everything under them is the same. If they do not match and the node is a single block, that block has diverged. If they do not match and the node is internal, both its subtrees are compared. Each comparison of a pair of nodes is one comparison. Different data never has matching hashes.

From the contents of the blocks of both replicas, find how many comparisons the reconciliation makes and which blocks have diverged. The tests include the source code of this site at two commits: a block is a file, and its content is a git identifier, or “-” if the file does not exist in that version.

Input

The first line holds n (1 ≤ n ≤ 5·10⁴). The second holds the n blocks of the first replica, the third those of the second: words of Latin letters, digits and the sign “-”, up to 12 characters long.

Output

The first line holds the number of comparisons. The second, the numbers of the diverged blocks in increasing order separated by spaces (numbered from one), or “-” if the replicas match.

Examples

Example 1

Input

8
162bb1f0 878c8d3f f0fe0865 269cb77c 04ceca25 baa3ba11 17640f86 be3c2e6e
162bb1f0 878c8d3f f0fe0865 269cb77c 04ceca25 5e93c4cd 17640f86 be3c2e6e

Output

7
6

Example 2

Input

5
0ff6d13d c30c45e6 8b53e711 80eb0941 a373041e
08ed8f88 c30c45e6 8b53e711 80eb0941 46553a59

Output

7
1 5

Limits

Time · Python: 3000 ms
Time · Go: 1000 ms
Memory: 256 MB
Judging: 10 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

Computing SHA-256 is not necessary. When do the hashes of two nodes differ, if different data never has matching hashes?

2Hint 2

A node differs if and only if its range contains at least one diverged block. How do you quickly find out whether the range [l, r) has such a block?

3The idea

Mark the diverged blocks and compute prefix sums of the marks: a range has a difference if the sum over it is not zero. Then repeat the reconciliation literally: a stack of ranges, starting with [0, n); each range taken off is one comparison; if there are no differences, go no further; if the range is a single block, record it; otherwise push the two subtrees.

4Walkthrough

In the first example there are eight blocks, and the sixth has diverged. The reconciliation: the root (differs), both halves of four blocks (the right differs), both quarters of the right half (the left differs, blocks 5 and 6), and finally blocks 5 and 6 separately. In all 1 + 2 + 2 + 2 = 7 comparisons instead of eight. The gain shows on large replicas: the seventh test has fifty thousand blocks and twenty differences, and a few hundred comparisons.

How many in general? Each differing internal node adds two comparisons, its children. There are at most as many differing nodes as diverged blocks times the depth of the tree, so there are O(d log n) comparisons for d differences, and at most 2n − 1 if everything differs. The worst case for the protocol is differences scattered evenly, as in the ninth test: each drags a separate path from the root. Neighbouring differences, as in the eighth, share the top of the path and cost less.

The sixth test is the source code of this site at two commits, 4224 files, 64 of them different. The binary tree finds them in 423 comparisons. Git itself reconciles differently, by directory, and in the article on the Merkle tree the same two commits come to 758 comparisons: a directory can have hundreds of children, and on a difference all of them are compared. The binary tree pays for this with depth: the path to a block is longer.

4+Solution

5Complexity

O(n) for the prefix sums and O(the number of comparisons) for the reconciliation, at most O(n).

6Common mistakes

Counting only differing nodes. A comparison costs the same whether the hashes match or not: the matching neighbour of a differing node was compared too. In the first example such a count gives 4 instead of 7.
Halving the range. In RFC 6962 the left subtree gets the largest power of two less than the length: for five blocks that is 4 and 1, not 2 and 3. In the second example the number of comparisons depends on this.
Forgetting matching replicas. The roots matched: one comparison, and “-” is printed.

Algorithms behind it

SYS Data structure Merkle tree Hashes of hashes: a fingerprint of the whole set, finding differences in a few comparisons and a proof of log n hashes. O(n) to build, O(log n) for a proof and its check 2 problems TEC Technique Prefix sums The sum of any segment in O(1) after one pass; the two-dimensional version gives the sum of any rectangle of a picture. O(n) to build, O(1) per query 2 problems