問題文

白く塗られた二次元平面を考えます。

まず、(x_1, y_1) からの距離が r 以下の部分を赤く塗ります。

そのあと、 x_2 ≦ x ≦ x_3, y_2 ≦ y ≦ y_3 を満たす (x, y) を青く塗ります。

なお、赤く塗られた後、更に青く塗られた部分は紫色になるとします。

赤く塗られた部分と青く塗られた部分が存在するかどうかをそれぞれ判定してください。

制約

• -100 ≦ x_1, y_1 ≦ 100
• -100 ≦ x_2 < x_3 ≦ 100
• -100 ≦ y_2 < y_3 ≦ 100
• 1 ≦ r ≦ 100
• 与えられる数は全て整数である。

入力例1

-1 -1 2
2 3 4 5

出力例1

YES
YES

赤い部分も青い部分もあります

入力例2

0 1 1
-2 0 4 3

出力例2

NO
YES

赤く塗られた部分は存在しません。

入力例3

0 0 5
-2 -2 2 1

出力例3

YES
NO

青く塗られた部分は存在しません。

入力例4

0 0 2
0 0 4 4

出力例4

YES
YES

円と長方形が重なっていますが赤く塗られた部分も青く塗られた部分も存在します。

入力例5

0 0 5
-4 -4 4 4

出力例5

YES
YES

問題文

高橋君は、ユークリッドの互除法というアルゴリズムを学びましたが、これがどのぐらいの速度で動くのか気になりました。

なので、以下のようなC言語のコードを書きました。

#include <stdio.h>

int counter = 0;
int gcd(int a, int b) {
    if (b == 0) return a;
    counter++;
    return gcd(b, a%b);
}

int main() {
    int a, b;
    scanf("%d %d", &a, &b);
    gcd(a, b);
    printf("%d\n", counter);
}

これは、2 つの整数を標準入力から受け取り、そのgcdをユークリッドの互除法で求め、求める際に何回再帰したかを出力するコードです。

あなたは、このプログラムにいろんな値を出力させたくなりました。

具体的には、K が与えられるので、このプログラムの出力が K となるような a, b を一組求めてください。

制約

• 1 ≦ K ≦ 40

ただし、以下の制約を満たすテストケースにすべて正解すれば 30 点が与えられる。

• 1 ≦ K ≦ 10

入力例1

1

出力例1

1 1

入力例2

3

出力例2

4 5

入力例3

12

出力例3

314159265 358979323

どの入出力例も、これ以外にも条件を満たす出力はたくさんあります。

問題文

N 個の整数 a_1, a_2, ..., a_N が与えられるので、一番小さいものを A 倍する、という操作を B 回行います。

この結果できた整数たちを昇順に並べ、順番に出力してください。

ただし出力するときは、出力したい数を 10^9 + 7 で割ったあまりを出力するようにしてください。

なお、10^9+7 で割ったあまりを昇順に並べる、というわけではないことに注意してください。

制約

• 1 ≦ N ≦ 50
• 1 ≦ a_i ≦ 1,000,000,000
• 1 ≦ A, B ≦ 1,000,000,000
• A は整数である

入力例1

3 10 3
1 99 10

出力例1

99
100
100

入力例2

2 100001 2
1 200000

出力例2

200000
199931

操作の結果、20000, 10000200001 の 2 つの整数ができます。10^9+7 で割ったあまりを出力することに注意してください。

入力例3

10 123 1000000000
394632992 714094234 84420 5 3439891 3395 35 58 5001 730

出力例3

954804718
385989482
948741792
268211139
100694402
492858064
955116743
68100851
154525400
479209143

問題文

長さ W の数列 a_1, a_2, ..., a_W と、長さ H の数列 b_1, b_2, ..., b_H が与えられます。

左から i 番目、上から j 番目のマス目には a_i + b_j が書き込まれた、W \times H のマス目を考えます。

Q 個の以下のようなクエリが与えられるので、処理してください。

• A, B が与えられるので、左から A 番目以内、上から B 番目以内のマス目たちの中から、選んだ部分が長方形になるように幾つかマス目を選んだ時の、選んだマス目の値の総和の最大値を出力。

なお、マス目を 1 つも選ばないことはできません。

制約

• 1 ≦ W, H ≦ 2000
• 1 ≦ Q ≦ 2000
• 1 ≦ A ≦ W
• 1 ≦ B ≦ H
• -100,000 ≦ a_i, b_i ≦ 100,000

入力例1

2 2
0 10
0 -1
4
1 1
1 2
2 1
2 2

出力例1

0
0
10
19

入力例2

3 3
1 10 100
1000 10000 100000
9
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3

出力例2

1001
11002
111003
2011
22022
222033
3111
33222
333333

入力例3

10 8
2 -4 0 0 -1 4 5 0 -3 0
2 0 0 -3 -5 -5 -4 -4
10
2 6
1 4
1 2
5 7
1 5
7 6
7 4
1 5
3 5
10 7

出力例3

8
8
6
8
8
34
34
8
8
36