Problem Statement 问题陈述

In AtCoder, the top $10$ rated players' usernames are displayed with a gold crown, and the top-rated player's username is displayed with a platinum crown.
在 AtCoder 中，评分最高的 $10$ 玩家的用户名以金冠显示，排名靠前的玩家的用户名以白金冠显示。

At the start of this contest, the usernames and ratings of the top $10$ rated players in the algorithm category are as follows:
在本次比赛开始时，算法类别中评分最高的 $10$ 玩家的用户名和评分如下：

tourist 3858
ksun48 3679
Benq 3658
Um_nik 3648
apiad 3638
Stonefeang 3630
ecnerwala 3613
mnbvmar 3555
newbiedmy 3516
semiexp 3481

You are given the username $S$ of one of these players. Print that player's rating.
您将获得其中一位玩家的用户名 $S$ 。打印该玩家的评分。

Constraints 约束

• $S$ is equal to one of the usernames of the top $10$ rated players in the algorithm category.
  $S$ 等于算法类别中评分最高的 $10$ 玩家的用户名之一。

Sample Input 1 示例输入 1

tourist

Sample Output 1 示例输出 1

3858

At the start of this contest, the rating of tourist in the algorithm category is $3858$.
在本次比赛开始时，算法类别中 游客的评分为 $3858$ 。

Sample Input 2 示例输入 2

semiexp

Sample Output 2 示例输出 2

3481

At the start of this contest, the rating of semiexp in the algorithm category is $3481$.
在本次比赛开始时， semiexp 在算法类别中的评分为 $3481$ 。

Problem Statement 问题陈述

You are given a positive integer $N$. Print a string of length $(N+1)$, $s_0s_1\ldots s_N$, defined as follows.
你得到一个正整数 $N$ 。打印长度 $(N+1)$ 为 、 $s_0s_1\ldots s_N$ 的字符串，定义如下。

For each $i = 0, 1, 2, \ldots, N$, 对于每个 $i = 0, 1, 2, \ldots, N$ ，

• if there is a divisor $j$ of $N$ that is between $1$ and $9$, inclusive, and $i$ is a multiple of $N/j$, then $s_i$ is the digit corresponding to the smallest such $j$ ($s_i$ will thus be one of 1, 2, ..., 9);
  如果有一个除数 $j$ $N$ 介 $1$ 于 和 $9$ 之间，包括 ，并且是 $i$ 的 $N/j$ 倍数，则 $s_i$ 是 对应于最小的 such $j$ 的数字（ $s_i$ 因此将是 ， 1 2 ， ...， 之一）; 9
• if no such $j$ exists, then $s_i$ is -.
  如果不存在这样的 $j$ 条件，则 $s_i$ 为 - .

Constraints 约束

• $1 \leq N \leq 1000$
• All input values are integers.
  所有输入值均为整数。

Sample Input 1 示例输入 1

12

Sample Output 1 示例输出 1

1-643-2-346-1

We will explain how to determine $s_i$ for some $i$.
我们将解释如何确定 $s_i$ 某些 $i$ .

• For $i = 0$, the divisors $j$ of $N$ between $1$ and $9$ such that $i$ is a multiple of $N/j$ are $1, 2, 3, 4, 6$. The smallest of these is $1$, so $s_0 =$ 1.
  对于 $i = 0$ ，是 的 $N/j$ 倍数的 之间的 $1$ $9$ $i$ 除数 $j$ 是 $1, 2, 3, 4, 6$ 。 $N$ 其中最小的是 $1$ ，所以 $s_0 =$ 1 。

• For $i = 4$, the divisors $j$ of $N$ between $1$ and $9$ such that $i$ is a multiple of $N/j$ are $3, 6$. The smallest of these is $3$, so $s_4 =$ 3.
  对于 $i = 4$ ，是 的 $N/j$ 倍数的 之间的 $1$ $9$ $i$ 除数 $j$ 是 $3, 6$ 。 $N$ 其中最小的是 $3$ ，所以 $s_4 =$ 3 。

• For $i = 11$, there are no divisors $j$ of $N$ between $1$ and $9$ such that $i$ is a multiple of $N/j$, so $s_{11} =$ -.
  对于 $i = 11$ ，没有 $N$ 之间的 $1$ 除数 $j$ 和 $9$ 是 $i$ 的 $N/j$ 倍数，所以 $s_{11} =$ - 。

Sample Input 2 示例输入 2

7

Sample Output 2 示例输出 2

17777771

Sample Input 3 示例输入 3

1

Sample Output 3 示例输出 3

11

Problem Statement 问题陈述

There is a $3\times3$ grid with numbers between $1$ and $9$, inclusive, written in each square. The square at the $i$-th row from the top and $j$-th column from the left $(1\leq i\leq3,1\leq j\leq3)$ contains the number $c _ {i,j}$.
每个方格中都有一个网 $3\times3$ 格， $1$ 其中 和 $9$ 之间有数字，包括 和。从顶部开始的第 $i$ -行和 $j$ 从左侧 $(1\leq i\leq3,1\leq j\leq3)$ 开始的第 - 列的正方形包含数字 $c _ {i,j}$ 。

The same number may be written in different squares, but not in three consecutive cells vertically, horizontally, or diagonally. More precisely, it is guaranteed that $c _ {i,j}$ satisfies all of the following conditions.

• $c _ {i,1}=c _ {i,2}=c _ {i,3}$ does not hold for any $1\leq i\leq3$.
• $c _ {1,j}=c _ {2,j}=c _ {3,j}$ does not hold for any $1\leq j\leq3$.
• $c _ {1,1}=c _ {2,2}=c _ {3,3}$ does not hold.
• $c _ {3,1}=c _ {2,2}=c _ {1,3}$ does not hold.

Takahashi will see the numbers written in each cell in random order. He will get disappointed when there is a line (vertical, horizontal, or diagonal) that satisfies the following condition.

• The first two squares he sees contain the same number, but the last square contains a different number.

Find the probability that Takahashi sees the numbers in all the squares without getting disappointed.

Constraints

• $c _ {i,j}\in\lbrace1,2,3,4,5,6,7,8,9\rbrace\ (1\leq i\leq3,1\leq j\leq3)$
• $c _ {i,1}=c _ {i,2}=c _ {i,3}$ does not hold for any $1\leq i\leq3$.
• $c _ {1,j}=c _ {2,j}=c _ {3,j}$ does not hold for any $1\leq j\leq3$.
• $c _ {1,1}=c _ {2,2}=c _ {3,3}$ does not hold.
• $c _ {3,1}=c _ {2,2}=c _ {1,3}$ does not hold.

Sample Input 1

3 1 9
2 5 6
2 7 1

Sample Output 1

0.666666666666666666666666666667

For example, if Takahashi sees $c _ {3,1}=2,c _ {2,1}=2,c _ {1,1}=3$ in this order, he will get disappointed.

On the other hand, if Takahashi sees $c _ {1,1},c _ {1,2},c _ {1,3},c _ {2,1},c _ {2,2},c _ {2,3},c _ {3,1},c _ {3,2},c _ {3,3}$ in this order, he will see all numbers without getting disappointed.

The probability that Takahashi sees all the numbers without getting disappointed is $\dfrac 23$. Your answer will be considered correct if the absolute error from the true value is at most $10 ^ {-8}$, so outputs such as $0.666666657$ and $0.666666676$ would also be accepted.

Sample Input 2

7 7 6
8 6 8
7 7 6

Sample Output 2

0.004982363315696649029982363316

Sample Input 3

3 6 7
1 9 7
5 7 5

Sample Output 3

0.4

Problem Statement

Takahashi is displaying a sentence with $N$ words in a window. All words have the same height, and the width of the $i$-th word $(1\leq i\leq N)$ is $L _ i$.

The words are displayed in the window separated by a space of width $1$. More precisely, when the sentence is displayed in a window of width $W$, the following conditions are satisfied.

• The sentence is divided into several lines.
• The first word is displayed at the beginning of the top line.
• The $i$-th word $(2\leq i\leq N)$ is displayed either with a gap of $1$ after the $(i-1)$-th word, or at the beginning of the line below the line containing the $(i-1)$-th word. It will not be displayed anywhere else.
• The width of each line does not exceed $W$. Here, the width of a line refers to the distance from the left end of the leftmost word to the right end of the rightmost word.

When Takahashi displayed the sentence in the window, the sentence fit into $M$ or fewer lines. Find the minimum possible width of the window.

Constraints

• $1\leq M\leq N\leq2\times10 ^ 5$
• $1\leq L _ i\leq10^9\ (1\leq i\leq N)$
• All input values are integers.

Sample Input 1

13 3
9 5 2 7 1 8 8 2 1 5 2 3 6

Sample Output 1

26

When the width of the window is $26$, you can fit the given sentence into three lines as follows.

You cannot fit the given sentence into three lines when the width of the window is $25$ or less, so print $26$.

Note that you should not display a word across multiple lines, let the width of a line exceed the width of the window, or rearrange the words.

Sample Input 2

10 1
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 2

10000000009

Note that the answer may not fit into a $32\operatorname{bit}$ integer.

Sample Input 3

30 8
8 55 26 97 48 37 47 35 55 5 17 62 2 60 23 99 73 34 75 7 46 82 84 29 41 32 31 52 32 60

Sample Output 3

189

Problem Statement

Takahashi is initially at his house and is about to visit Aoki's house.

There are $N$ bus stops numbered $1$ to $N$ between the two houses, and Takahashi can move between them in the following ways:

• He can walk from his house to bus stop $1$ in $X$ units of time.
• For each $i = 1, 2, \ldots, N-1$, a bus departs from bus stop $i$ at each time that is a multiple of $P_i$, and by taking this bus, he can get to bus stop $(i+1)$ in $T_i$ units of time. Here, the constraints guarantee that $1 \leq P_i \leq 8$.
• Takahashi can walk from bus stop $N$ to Aoki's house in $Y$ units of time.

For each $i = 1, 2, \ldots, Q$, process the following query.

Find the earliest time that Takahashi can arrive at Aoki's house when he leaves his house at time $q_i$.

Note that if he arrives at a bus stop exactly at the departure time of a bus, he can take that bus.

Constraints

• $2 \leq N \leq 10^5$
• $1 \leq X, Y \leq 10^9$
• $1 \leq P_i \leq 8$
• $1 \leq T_i \leq 10^9$
• $1 \leq Q \leq 2 \times 10^5$
• $0 \leq q_i \leq 10^9$
• All input values are integers.

Sample Input 1

4 2 3
5 4
6 6
3 1
7
13
0
710511029
136397527
763027379
644706927
447672230

Sample Output 1

34
22
710511052
136397548
763027402
644706946
447672250

For the first query, Takahashi can move as follows to arrive at Aoki's house at time $34$.

• Leave his house at time $13$.
• Walk from his house and arrive at bus stop $1$ at time $15$.
• Take the bus departing from bus stop $1$ at time $15$ and arrive at bus stop $2$ at time $19$.
• Take the bus departing from bus stop $2$ at time $24$ and arrive at bus stop $3$ at time $30$.
• Take the bus departing from bus stop $3$ at time $30$ and arrive at bus stop $4$ at time $31$.
• Walk from bus stop $4$ and arrive at Aoki's house at time $34$.

For the second query, Takahashi can move as follows and arrive at Aoki's house at time $22$.

• Leave his house at time $0$.
• Walk from his house and arrive at bus stop $1$ at time $2$.
• Take the bus departing from bus stop $1$ at time $5$ and arrive at bus stop $2$ at time $9$.
• Take the bus departing from bus stop $2$ at time $12$ and arrive at bus stop $3$ at time $18$.
• Take the bus departing from bus stop $3$ at time $18$ and arrive at bus stop $4$ at time $19$.
• Walk from bus stop $4$ and arrive at Aoki's house at time $22$.