Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
正整数 A,B が与えられます。
A^B+B^A の値を出力してください。
制約
- 2 \leq A \leq B \leq 9
- 入力される数値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
A B
出力
答えを整数として出力せよ。
入力例 1
2 8
出力例 1
320
A = 2, B = 8 のとき、A^B = 256, B^A = 64 なので A^B + B^A = 320 です。
入力例 2
9 9
出力例 2
774840978
入力例 3
5 6
出力例 3
23401
Score : 100 points
Problem Statement
You are given positive integers A and B.
Print the value A^B+B^A.
Constraints
- 2 \leq A \leq B \leq 9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
A B
Output
Print the answer as an integer.
Sample Input 1
2 8
Sample Output 1
320
For A = 2, B = 8, we have A^B = 256, B^A = 64, so A^B + B^A = 320.
Sample Input 2
9 9
Sample Output 2
774840978
Sample Input 3
5 6
Sample Output 3
23401
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
文字列 S が与えられます。
S の連続する部分文字列のうち、回文であるものの長さの最大値を求めてください。
ただし、S の連続する部分文字列であって回文であるものは常に存在します。
制約
- S は長さ 2 以上 100 以下の英大文字からなる文字列
入力
入力は以下の形式で標準入力から与えられる。
S
出力
答えを出力せよ。
入力例 1
TOYOTA
出力例 1
5
TOYOTA の連続する部分文字列 TOYOT は長さ 5 の回文です。
TOYOTA の唯一の長さ 6 の連続する部分文字列 TOYOTA は回文でないので、5 を出力します。
入力例 2
ABCDEFG
出力例 2
1
すべての長さ 1 の連続する部分文字列は回文です。
入力例 3
AAAAAAAAAA
出力例 3
10
Score : 200 points
Problem Statement
You are given a string S.
Find the maximum length of a contiguous substring of S that is a palindrome.
Note that there is always a contiguous substring of S that is a palindrome.
Constraints
- S is a string of length between 2 and 100, inclusive, consisting of uppercase English letters.
Input
The input is given from Standard Input in the following format:
S
Output
Print the answer.
Sample Input 1
TOYOTA
Sample Output 1
5
TOYOT, a contiguous substring of TOYOTA, is a palindrome of length 5.
TOYOTA, the only length-6 contiguous substring of TOYOTA, is not a palindrome, so print 5.
Sample Input 2
ABCDEFG
Sample Output 2
1
Every contiguous substring of length 1 is a palindrome.
Sample Input 3
AAAAAAAAAA
Sample Output 3
10
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
この問題は G 問題の簡易版です。
3 個のリールからなるスロットがあります。
i 番目のリールの配列は文字列 S_i によって表されます。ここで、S_i は数字のみからなる長さ M の文字列です。
それぞれのリールには対応するボタンがついています。高橋君は各非負整数 t について、スロットが回り始めてからちょうど t 秒後にボタンを 1 つ選んで押す、または何もしないことができます。
スロットが回り始めてから t 秒後に i 番目のリールに対応するボタンを押すと、i 番目のリールは S_i の (t \bmod M)+1 文字目を表示して止まります。
ただし、t \bmod M で t を M で割ったあまりを表します。
高橋君は全てのリールを止めた上で、表示されている文字が全て同じであるようにしたいです。
高橋君が目標を達成できるように全てのリールを止めるまでに、スロットが回り始めてから最小で何秒かかるかを求めてください。
そのようなことが不可能であればそのことを報告してください。
制約
- 1 \leq M \leq 100
- M は整数
- S_i は数字のみからなる長さ M の文字列
入力
入力は以下の形式で標準入力から与えられる。
M S_1 S_2 S_3
出力
全てのリールを止めた上で、表示されている文字が全て同じであるようにすることができないなら -1 を出力せよ。
できるなら、スロットが回り始めてからそのような状態にするまでに最小で何秒かかるか出力せよ。
入力例 1
10 1937458062 8124690357 2385760149
出力例 1
6
高橋君は次のようにそれぞれのリールを止めることでスロットが回り始めてから 6 秒後にリールに表示される文字を 8 で揃えることができます。
- スロットの回転開始から 0 秒後に 2 番目のリールに対応するボタンを押します。2 番目のリールは S_2 の (0 \bmod 10)+1=1 文字目である
8を表示して止まります。 - スロットの回転開始から 2 秒後に 3 番目のリールに対応するボタンを押します。3 番目のリールは S_3 の (2 \bmod 10)+1=3 文字目である
8を表示して止まります。 - スロットの回転開始から 6 秒後に 1 番目のリールに対応するボタンを押します。1 番目のリールは S_1 の (6 \bmod 10)+1=7 文字目である
8を表示して止まります。
5 秒以下で全てのリールに表示されている文字を揃える方法はないため、6 を出力します。
入力例 2
20 01234567890123456789 01234567890123456789 01234567890123456789
出力例 2
20
全てのリールを止めた上で、表示されている文字を揃える必要がある事に注意してください。
入力例 3
5 11111 22222 33333
出力例 3
-1
表示されている文字が全て同じであるようにリールを止めることはできません。
このとき -1 を出力してください。
Score : 300 points
Problem Statement
This problem is an easier version of Problem G.
There is a slot machine with three reels.
The arrangement of symbols on the i-th reel is represented by the string S_i. Here, S_i is a string of length M consisting of digits.
Each reel has a corresponding button. For each non-negative integer t, Takahashi can either choose and press one button or do nothing exactly t seconds after the reels start spinning.
If he presses the button corresponding to the i-th reel exactly t seconds after the reels start spinning, the i-th reel will stop and display the ((t \bmod M)+1)-th character of S_i.
Here, t \bmod M denotes the remainder when t is divided by M.
Takahashi wants to stop all the reels so that all the displayed characters are the same.
Find the minimum possible number of seconds from the start of the spin until all the reels are stopped so that his goal is achieved.
If this is impossible, report that fact.
Constraints
- 1 \leq M \leq 100
- M is an integer.
- S_i is a string of length M consisting of digits.
Input
The input is given from Standard Input in the following format:
M S_1 S_2 S_3
Output
If it is impossible to stop all the reels so that all the displayed characters are the same, print -1.
Otherwise, print the minimum possible number of seconds from the start of the spin until such a state is achieved.
Sample Input 1
10 1937458062 8124690357 2385760149
Sample Output 1
6
Takahashi can stop each reel as follows so that 6 seconds after the reels start spinning, all the reels display 8.
- Press the button corresponding to the second reel 0 seconds after the reels start spinning. The second reel stops and displays
8, the ((0 \bmod 10)+1=1)-st character of S_2. - Press the button corresponding to the third reel 2 seconds after the reels start spinning. The third reel stops and displays
8, the ((2 \bmod 10)+1=3)-rd character of S_3. - Press the button corresponding to the first reel 6 seconds after the reels start spinning. The first reel stops and displays
8, the ((6 \bmod 10)+1=7)-th character of S_1.
There is no way to make the reels display the same character in 5 or fewer seconds, so print 6.
Sample Input 2
20 01234567890123456789 01234567890123456789 01234567890123456789
Sample Output 2
20
Note that he must stop all the reels and make them display the same character.
Sample Input 3
5 11111 22222 33333
Sample Output 3
-1
It is impossible to stop the reels so that all the displayed characters are the same.
In this case, print -1.
Time Limit: 2.5 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
座標平面上に 1 から N の番号がついた N 人の人がいます。
人 1 は原点にいます。
次の形式の情報が M 個与えられます。
- 人 A_i から見て、人 B_i は、x 軸正方向に X_i、y 軸正方向に Y_i 離れた位置にいる
それぞれの人がいる座標を求めてください。一意に定まらないときはそのことを報告してください。
制約
- 1 \leq N \leq 2\times 10^5
- 0 \leq M \leq 2\times 10^5
- 1\leq A_i, B_i \leq N
- A_i \neq B_i
- -10^9 \leq X_i,Y_i \leq 10^9
- 入力は全て整数である
- 与えられる情報は矛盾しない
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 B_1 X_1 Y_1 \vdots A_M B_M X_M Y_M
出力
N 行出力せよ。
人 i のいる座標が一意に定まらないとき、i 行目には undecidable と出力せよ。
人 i のいる座標が (s_i,t_i) と一意に定まるとき、i 行目には s_i,t_i をこの順に空白区切りで出力せよ。
入力例 1
3 2 1 2 2 1 1 3 -1 -2
出力例 1
0 0 2 1 -1 -2
3 人の位置関係は下図のようになっています。
入力例 2
3 2 2 1 -2 -1 2 3 -3 -3
出力例 2
0 0 2 1 -1 -2
3 人の位置関係は下図のようになっています。
入力例 3
5 7 1 2 0 0 1 2 0 0 2 3 0 0 3 1 0 0 2 1 0 0 3 2 0 0 4 5 0 0
出力例 3
0 0 0 0 0 0 undecidable undecidable
同じ情報が複数回与えられたり、同じ座標に複数の人がいることもあります。
Score : 400 points
Problem Statement
There are N people numbered 1 to N on a coordinate plane.
Person 1 is at the origin.
You are given M pieces of information in the following form:
- From person A_i's perspective, person B_i is X_i units away in the positive x-direction and Y_i units away in the positive y-direction.
Determine the coordinates of each person. If the coordinates of a person cannot be uniquely determined, report that fact.
Constraints
- 1 \leq N \leq 2\times 10^5
- 0 \leq M \leq 2\times 10^5
- 1\leq A_i, B_i \leq N
- A_i \neq B_i
- -10^9 \leq X_i,Y_i \leq 10^9
- All input values are integers.
- The given information is consistent.
Input
The input is given from Standard Input in the following format:
N M A_1 B_1 X_1 Y_1 \vdots A_M B_M X_M Y_M
Output
Print N lines.
If the coordinates of person i cannot be uniquely determined, the i-th line should contain undecidable.
If they can be uniquely determined as (s_i,t_i), the i-th line should contain s_i and t_i in this order, separated by a space.
Sample Input 1
3 2 1 2 2 1 1 3 -1 -2
Sample Output 1
0 0 2 1 -1 -2
The figure below shows the positional relationship of the three people.
Sample Input 2
3 2 2 1 -2 -1 2 3 -3 -3
Sample Output 2
0 0 2 1 -1 -2
The figure below shows the positional relationship of the three people.
Sample Input 3
5 7 1 2 0 0 1 2 0 0 2 3 0 0 3 1 0 0 2 1 0 0 3 2 0 0 4 5 0 0
Sample Output 3
0 0 0 0 0 0 undecidable undecidable
The same piece of information may be given multiple times, and multiple people may be at the same coordinates.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 475 点
問題文
そうめん流しのイベントに N 人の人が集まりました。人は一列に並んでおり、先頭から順に 1 から N の番号がついています。
そうめん流しでは次の出来事が M 回起こります。
- 時刻 T_i に 量 W_i のそうめんを流す。列の先頭にいる人がその全てを得る（誰も列に並んでいない場合は、誰もそのそうめんを得ない）。その人はいったん列から外れ、時刻 T_i+S_i に列の元の位置に戻ってくる。
時刻 X に列に戻ってくる人は、時刻 X には列に並んでいるとみなします。
M 回の出来事が全て行われたあと、それぞれの人が合計でどれだけそうめんを得ることができたか答えてください。
制約
- 1 \leq N \leq 2\times 10^5
- 1 \leq M \leq 2\times 10^5
- 0 <T_1 <\ldots < T_M \leq 10^9
- 1 \leq S_i \leq 10^9
- 1 \leq W_i \leq 10^9
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M T_1 W_1 S_1 \vdots T_M W_M S_M
出力
N 行出力せよ。 i 行目には人 i が得たそうめんの量を出力せよ。
入力例 1
3 5 1 1 3 2 10 100 4 100 10000 10 1000 1000000000 100 1000000000 1
出力例 1
101 10 1000
次のように進行します。
- 時刻 1 に量 1 のそうめんが流される。列には人 1,2,3 が並んでおり、先頭の人 1 がそうめんを得て列から外れる。
- 時刻 2 に量 10 のそうめんが流される。列には人 2,3 が並んでおり、先頭の人 2 がそうめんを得て列から外れる。
- 時刻 4 に人 1 が列に戻ってくる。
- 時刻 4 に量 100 のそうめんが流される。列には人 1,3 が並んでおり、先頭の人 1 がそうめんを得て列から外れる。
- 時刻 10 に量 1000 のそうめんが流される。列には人 3 が並んでおり、先頭の人 3 がそうめんを得て列から外れる。
- 時刻 100 に量 1000000000 のそうめんが流される。列には誰も並んでいないため、誰もこのそうめんを得ない。
- 時刻 102 に人 2 が列に戻ってくる。
- 時刻 10004 に人 1 が列に戻ってくる。
- 時刻 1000000010 に人 3 が列に戻ってくる。
それぞれの人が得たそうめんの量の合計は、101,10,1000 です。
入力例 2
3 1 1 1 1
出力例 2
1 0 0
入力例 3
1 8 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 6 6 7 7 7 8 8 8
出力例 3
15
Score : 475 points
Problem Statement
There are N people gathered for an event called Flowing Noodles. The people are lined up in a row, numbered 1 to N in order from front to back.
During the event, the following occurrence happens M times:
- At time T_i, a quantity W_i of noodles is flown down. The person at the front of the row gets all of it (if no one is in the row, no one gets it). That person then steps out of the row and returns to their original position in the row at time T_i+S_i.
A person who returns to the row at time X is considered to be in the row at time X.
After all the M occurrences, report the total amount of noodles each person has got.
Constraints
- 1 \leq N \leq 2\times 10^5
- 1 \leq M \leq 2\times 10^5
- 0 <T_1 <\ldots < T_M \leq 10^9
- 1 \leq S_i \leq 10^9
- 1 \leq W_i \leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M T_1 W_1 S_1 \vdots T_M W_M S_M
Output
Print N lines. The i-th line should contain the amount of noodles person i has got.
Sample Input 1
3 5 1 1 3 2 10 100 4 100 10000 10 1000 1000000000 100 1000000000 1
Sample Output 1
101 10 1000
The event proceeds as follows:
- At time 1, a quantity 1 of noodles is flown down. People 1, 2, and 3 are in the row, and the person at the front, person 1, gets the noodles and steps out of the row.
- At time 2, a quantity 10 of noodles is flown down. People 2 and 3 are in the row, and the person at the front, person 2, gets the noodles and steps out of the row.
- At time 4, person 1 returns to the row.
- At time 4, a quantity 100 of noodles is flown down. People 1 and 3 are in the row, and the person at the front, person 1, gets the noodles and steps out of the row.
- At time 10, a quantity 1000 of noodles is flown down. Only person 3 is in the row, and the person at the front, person 3, gets the noodles and steps out of the row.
- At time 100, a quantity 1000000000 of noodles is flown down. No one is in the row, so no one gets these noodles.
- At time 102, person 2 returns to the row.
- At time 10004, person 1 returns to the row.
- At time 1000000010, person 3 returns to the row.
The total amounts of noodles people 1, 2, and 3 have got are 101, 10, and 1000, respectively.
Sample Input 2
3 1 1 1 1
Sample Output 2
1 0 0
Sample Input 3
1 8 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 6 6 7 7 7 8 8 8
Sample Output 3
15
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 550 点
問題文
数直線上の座標 0 から座標 X_N まで行き、折り返して座標 0 まで帰ってくる計画を立てています。ただし、往路では正の方向、復路では負の方向にしか進めません。
移動は車で行います。車は距離 1 進むごとに 1 リットルの燃料を消費します。燃料は H リットルまで所持することができ、燃料を所持していない状態で進むことはできません。
各 i = 1, 2, \ldots, N-1 について、座標 X_i にはガソリンスタンドがあり、P_i 円払うと F_i リットルの燃料が得られます。ただし、H リットルを超えて燃料を所持することはできません。より厳密には、x リットルの燃料を持っているときに座標 X_i にあるガソリンスタンドを使うと P_i 円を払う必要があり、持っている燃料は \min(x + F_i, H) リットルとなります。 各ガソリンスタンドは、往路と復路で合わせて 1 回までしか使うことができません。
はじめに燃料を H リットル所持しているとき、この計画を達成することができるか判定し、可能ならば必要な金額の最小値を求めてください。
制約
- 1 \leq N, H \leq 300
- 0 < X_1 < X_2 < \ldots < X_N \leq 10^5
- 1 \leq P_i \leq 10^5
- 1 \leq F_i \leq H
- 入力される数値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N H
X_1 X_2 \ldots X_N
P_1 F_1
P_2 F_2
\vdots
P_{N-1} F_{N-1}
出力
計画を達成できる場合は必要な金額の最小値を、できない場合は -1 を出力せよ。
入力例 1
4 10 2 5 9 11 8 10 5 8 4 9
出力例 1
9
往路で座標 5 の、復路で座標 9 のガソリンスタンドを用いることにより合計 9 円払うことで計画を達成することができます。
計画を達成するためにかかる金額を 8 円以下にすることはできません。往路と復路で同じガソリンスタンドを使うことができないことに注意してください。
入力例 2
1 1 100000
出力例 2
-1
入力例 3
5 20 4 13 16 18 23 1 16 2 8 4 11 8 13
出力例 3
13
Score : 550 points
Problem Statement
You are planning to travel from coordinate 0 to coordinate X_N on a number line, then turn around and return to coordinate 0. Here, you can only move in the positive direction on the outbound trip and in the negative direction on the return trip.
You will travel by car. The car consumes one liter of fuel for every unit distance it travels. You can carry up to H liters of fuel and cannot move without fuel.
For each i = 1, 2, \ldots, N-1, there is a gas station at coordinate X_i, where you can get F_i liters of fuel for P_i yen. However, you cannot carry more than H liters of fuel. More precisely, if you have x liters of fuel and use the gas station at coordinate X_i, you must pay P_i yen, and your amount of fuel becomes \min(x + F_i, H) liters. Each gas station can be used at most once in total during the round trip.
Determine if you can achieve this plan when you initially have H liters of fuel, and if it is possible, find the minimum amount of money required.
Constraints
- 1 \leq N, H \leq 300
- 0 < X_1 < X_2 < \ldots < X_N \leq 10^5
- 1 \leq P_i \leq 10^5
- 1 \leq F_i \leq H
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N H
X_1 X_2 \ldots X_N
P_1 F_1
P_2 F_2
\vdots
P_{N-1} F_{N-1}
Output
If the plan can be achieved, print the minimum amount of money required; otherwise, print -1.
Sample Input 1
4 10 2 5 9 11 8 10 5 8 4 9
Sample Output 1
9
You can achieve the plan by using the gas station at coordinate 5 on the outbound trip and the one at coordinate 9 on the return trip, paying a total of 9 yen.
It is impossible to achieve the plan by paying 8 yen or less. Note that you cannot use the same gas station on both the outbound and return trips.
Sample Input 2
1 1 100000
Sample Output 2
-1
Sample Input 3
5 20 4 13 16 18 23 1 16 2 8 4 11 8 13
Sample Output 3
13
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
この問題は C 問題の強化版です。リールの個数が 3 個から N 個になり、M の上限が大きくなっています。
N 個のリールからなるスロットがあります。
i 番目のリールの配列は文字列 S_i によって表されます。ここで、S_i は数字のみからなる長さ M の文字列です。
それぞれのリールには対応するボタンがついています。高橋君は各非負整数 t について、スロットが回り始めてからちょうど t 秒後にボタンを 1 つ選んで押す、または何もしないことができます。
スロットが回り始めてから t 秒後に i 番目のリールに対応するボタンを押すと、i 番目のリールは S_i の (t \bmod M)+1 文字目を表示して止まります。
ただし、t \bmod M で t を M で割ったあまりを表します。
高橋君は全てのリールを止めた上で、表示されている文字が全て同じであるようにしたいです。
高橋君が目標を達成できるように全てのリールを止めるまでに、スロットが回り始めてから最小で何秒かかるかを求めてください。
そのようなことが不可能であればそのことを報告してください。
制約
- 1 \leq N \leq 100
- 1 \leq M \leq 10^5
- N,M は整数
- S_i は数字のみからなる長さ M の文字列
入力
入力は以下の形式で標準入力から与えられる。
N M S_1 \vdots S_N
出力
全てのリールを止めた上で、表示されている文字が全て同じであるようにすることができないなら -1 を出力せよ。
できるなら、スロットが回り始めてからそのような状態にするまでに最小で何秒かかるか出力せよ。
入力例 1
3 10 1937458062 8124690357 2385760149
出力例 1
6
高橋君は次のようにそれぞれのリールを止めることでスロットが回り始めてから 6 秒後にリールに表示される文字を 8 で揃えることができます。
- スロットの回転開始から 0 秒後に 2 番目のリールに対応するボタンを押します。2 番目のリールは S_2 の (0 \bmod 10)+1=1 文字目である
8を表示して止まります。 - スロットの回転開始から 2 秒後に 3 番目のリールに対応するボタンを押します。3 番目のリールは S_3 の (2 \bmod 10)+1=3 文字目である
8を表示して止まります。 - スロットの回転開始から 6 秒後に 1 番目のリールに対応するボタンを押します。1 番目のリールは S_1 の (6 \bmod 10)+1=7 文字目である
8を表示して止まります。
5 秒以下で全てのリールに表示されている文字を揃える方法はないため、6 を出力します。
入力例 2
10 20 01234567890123456789 01234567890123456789 01234567890123456789 01234567890123456789 01234567890123456789 01234567890123456789 01234567890123456789 01234567890123456789 01234567890123456789 01234567890123456789
出力例 2
90
全てのリールを止めた上で、表示されている文字を揃える必要がある事に注意してください。
入力例 3
5 10 0000000000 1111111111 2222222222 3333333333 4444444444
出力例 3
-1
表示されている文字が全て同じであるようにリールを止めることはできません。
このとき -1 を出力してください。
入力例 4
10 20 14159265358979323846 26433832795028841971 69399375105820974944 59230781640628620899 86280348253421170679 82148086513282306647 09384460955058223172 53594081284811174502 84102701938521105559 64462294895493038196
出力例 4
11
Score : 600 points
Problem Statement
This problem is a harder version of Problem C, with N reels instead of three and a greater upper limit for M.
There is a slot machine with N reels.
The arrangement of symbols on the i-th reel is represented by the string S_i. Here, S_i is a string of length M consisting of digits.
Each reel has a corresponding button. For each non-negative integer t, Takahashi can either choose and press one button or do nothing exactly t seconds after the reels start spinning.
If he presses the button corresponding to the i-th reel exactly t seconds after the reels start spinning, the i-th reel will stop and display the ((t \bmod M)+1)-th character of S_i.
Here, t \bmod M denotes the remainder when t is divided by M.
Takahashi wants to stop all the reels so that all the displayed characters are the same.
Find the minimum possible number of seconds from the start of the spin until all the reels are stopped so that his goal is achieved.
If this is impossible, report that fact.
Constraints
- 1 \leq N \leq 100
- 1 \leq M \leq 10^5
- N and M are integers.
- S_i is a string of length M consisting of digits.
Input
The input is given from Standard Input in the following format:
N M S_1 \vdots S_N
Output
If it is impossible to stop all the reels so that all the displayed characters are the same, print -1.
Otherwise, print the minimum possible number of seconds from the start of the spin until such a state is achieved.
Sample Input 1
3 10 1937458062 8124690357 2385760149
Sample Output 1
6
Takahashi can stop each reel as follows so that 6 seconds after the reels start spinning, all the reels display 8.
- Press the button corresponding to the second reel 0 seconds after the reels start spinning. The second reel stops and displays
8, the ((0 \bmod 10)+1=1)-st character of S_2. - Press the button corresponding to the third reel 2 seconds after the reels start spinning. The third reel stops and displays
8, the ((2 \bmod 10)+1=3)-rd character of S_3. - Press the button corresponding to the first reel 6 seconds after the reels start spinning. The first reel stops and displays
8, the ((6 \bmod 10)+1=7)-th character of S_1.
There is no way to make the reels display the same character in 5 or fewer seconds, so print 6.
Sample Input 2
10 20 01234567890123456789 01234567890123456789 01234567890123456789 01234567890123456789 01234567890123456789 01234567890123456789 01234567890123456789 01234567890123456789 01234567890123456789 01234567890123456789
Sample Output 2
90
Note that he must stop all the reels and make them display the same character.
Sample Input 3
5 10 0000000000 1111111111 2222222222 3333333333 4444444444
Sample Output 3
-1
It is impossible to stop the reels so that all the displayed characters are the same.
In this case, print -1.
Sample Input 4
10 20 14159265358979323846 26433832795028841971 69399375105820974944 59230781640628620899 86280348253421170679 82148086513282306647 09384460955058223172 53594081284811174502 84102701938521105559 64462294895493038196
Sample Output 4
11