- 16

## What will I learn?

CryptographyMathematicsSecret sharingInterpolationPolynomials

## 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`(

`k`<

**at least any**of the secret are necessary to reveal it. This allows to retrieve the secret even with a few agents missing in action.

`k`partsFinally, 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

where each character is

**identified by its index**from

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

Each agent 00

**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 + 44Agent 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**The code number

`N`lines:`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

`N`<

It is guaranteed that

`N`≥

`k`the threshold that was used to share the secret.

All the

`Si`have the same length <

Example

Input

2 005 Lvb 004 Xn_

Output

SIS

A higher resolution is required to access the IDE

Join the CodinGame community on Discord to chat about puzzle contributions, challenges, streams, blog articles - all that good stuff!

JOIN US ON DISCORD Online Participants