Practice Cryptography and Polynomials with the exercise "Her Majesty's well shared secret"

Learning Opportunities

This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.

Statement

Goal

Some top secret information has been shared between Her Majesty's double-zero agents. Time has come to reveal it! But in order to avoid the secret to fall too easily into the hands of the enemy, a deeply thought process has been used to share it.

First, each of the nine double-zero agents (from 001 to 009) only carries a distinct "part" of the secret.
Also, there is a threshold k (1 < k < 9) such that at least any k parts of the secret are necessary to reveal it. This allows to retrieve the secret even with a few agents missing in action.
Finally, the knowledge of less than k parts does not allow to derive any information about the secret! (There might be some statistical biases for some poorly chosen parameters, but in general there is none.) The enemy has to capture or hire at least k agents to learn anything.

Your task is to figure out how to reveal the secret given at least k parts.
The following describes the secret sharing process in details.

First of all, the secret message S is written using the following alphabet of 53 characters:
abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_
where each character is identified by its index from 0 to 52: a=0, b=1, ..., underscore=52.

Given a threshold k ≥ 2, the secret sharing process is the following:
For each index i of S, a polynomial

P[i] = A[i,k-1]⋅X^(k-1) + A[i,k-2]⋅X^(k-2) + ... + A[i,1]⋅X + S[i]

is defined where the coefficients A[..] are chosen randomly between 0 and 52 (inclusive) with the additional constraint A[i,k-1]>0.
Each agent 00x is provided with the string representing the values [P[0](x)%53, P[1](x)%53, ...]. This constitutes his part of the secret, while the secret itself is the string representing [P[0](0), P[1](0), ...].

Example: Consider k = 2 and S = "SIS" = [44, 34, 44].
For each character we pick a random polynomial of degree 1 with the corresponding character as constant coefficient:

P0 = 41X + 44, P1 = 8X + 34, P2 = 2X + 44

Agent 001 receives [P0(1)%53, P1(1)%53, P2(1)%53] = [32, 42, 46] = GQU;
Agent 002 receives [P0(2)%53, P1(2)%53, P2(2)%53] = [20, 50, 48] = uYW;
...

Input

Line 1: An integer N, the number of parts gathered.
Next N lines: The code number Ci of an agent followed by his part Si of the secret. All the Si have the same size.

Output

One single string corresponding to the revealed secret.

Constraints

1 < N < 9
It is guaranteed that N ≥ k the threshold that was used to share the secret.
All the Si have the same length <300.

Example

Input

2
005 Lvb
004 Xn_

Output

SIS

Solve it

A higher resolution is required to access the IDE