全国高等学校パソコンコンクール
プログラミング部門 予選問題
２０２１年９月１１日(土)１３時３０分～１６時３０分

全国高等学校パソコンコンクール実行委員会

問題１

マウスの移動距離（２点）

パソコンを操作するときに使われる、マウスの移動距離を表す単位に「ミッキー」があります。１ミッキーは、100 分の 1 インチなので、およそ 0.25 ミリメートルです。4 ミッキーなら移動距離はおよそ１ミリメートルになります。

課題
マウスの移動距離がミッキー単位で与えられたとき、それが何ミリメートルであるかを求めるプログラ
ムを作成せよ。ただし、1 ミッキーは正確に 0.25 ミリメートルであるとして計算すること。

入力
入力は以下の形式で与えられる。
d
１行にミッキー単位でのマウスの移動距離d(4≦d≦400)が与えられる。ただし、dは４の倍数である。

出力
マウスの移動距離をミリメートル単位に変換した値を、１行に出力する。

入出力例
入力例１4出力例１1

入力例２400

出力例２100

問題２

ミニ絵合わせゲーム（３点）

カクマ君のお気に入りは絵柄が書かれたカードを使って遊ぶ絵合わせゲームです。このゲームには２６種類の絵柄があり、それぞれの絵柄が書かれたカードを２枚ずつ、合計５２枚のカードを使います。
絵合わせは一人で行うゲームで、初めにすべてのカードを絵柄が見えないようにして机におきます。次にそれらのカードから２枚選び、絵柄が同じ場合は机から取り除きます。絵柄が異なる場合は、選んだ２枚のカードを絵柄が見えないようにして机に戻します。机からすべてのカードがなくなったらゲーム終了です。
カクマ君は妹のヤエちゃんにこの絵合わせゲームを教えてあげることにしました。しかし、５２枚のカードでは難しいため、４枚のカードを選んでミニ絵合わせゲームを作ることにしました。ミニ絵合わせゲームのルールが絵合わせゲームと同じルールのとき、カクマ君が選んだカードはゲームを終了できる組み合わせになっているでしょうか。

課題
４枚のカードの絵柄がそれぞれ与えられる。これらのカードでミニ絵合わせゲームが終了できるかどうかを判定するプログラムを作成せよ。ただし、２６種類の絵柄は１から２６までの整数で表されているものとする。

入力
入力は以下の形式で与えられる。
a1 a2 a3 a4
１行に４枚のカードの絵柄の種類を表す整数ai(1≦ai≦26)が与えられる。ただし、同じ値が３つ以上与えられることはない。

出力
ミニ絵合わせゲームを終了できる場合は「1」を、できない場合は「0」を１行に出力する。

入出力例
入力例１1 2 1 2

出力例１1

入力例２5 7 5 8

出力例２0問題３ダイヤル錠（４点）

PCK 君の家のポストには特別なダイヤル錠が付いています。このダイヤル錠には 0 から 9 までの数字が時計回りに並んだ回転式のダイヤルがあります。ダイヤルの上部に赤い目印が付いていて、数字が目印に合うとカチッと１回音が鳴ります。
このダイヤル錠には、錠を開けるための所定の数字列が暗証番号として設定されています。開錠するには、0 を目印に合わせた状態から、ダイヤルを回して暗証番号に含まれる数字を順番に目印に合わせていきます。すべての数字を合わせるまでにカチッと鳴る音の数が最小の場合にのみ、このダイヤル錠を開錠することができます。
たとえば、暗証番号が 374 の場合は、図に示すように 0 を目印に合わせた状態から、反時計回りに 3 まで回し、次に反時計回りに 7 まで、最後に時計回りに 4 まで回せば、全部で 10 回音が鳴ります。3、7、4 の順番で合わせるときに音が鳴る回数は 10 回が最小なので、この方法でダイヤルを回すとダイヤル錠が開錠します。

反時計回り

反時計回り

時計回り

課題
ダイヤル錠の暗証番号が与えられたとき、数字 0 を目印に合わせた状態から開錠するまでに鳴る音の回数を計算するプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
N
a1 a2 … aN
１行目に暗証番号の列に含まれる数字の個数N(1≦N≦1,000)が与えられる。２行目に暗証番号に含まれる数字ai(0≦ai≦9)が順番に与えられる。ただし、同じ数字が連続して与えられることはない。また、最初の数字a1は0以外の数字である。

出力
開錠するまでに鳴る音の回数を１行に出力する。

入出力例
入力例１3

出力例１103 7 4
入力例２4
1 2 3 9出力例２7問題４乗り継ぎ（５点）

PCK 君はアイヅ駅周辺に住んでおり、キタカタ駅の近くの学校に通っています。お父さんはアイヅ駅とキタカタ駅の間にあるシオカワ駅で働いています。
今朝お父さんはお弁当を忘れてしまいました。PCK 君は初めにアイヅ駅から電車に乗り、次にシオカワ駅でいったん下車して駅にいるお父さんにお弁当を渡してから、そこからもう一度電車に乗ってキタカタ駅に向かおうと考えています。しかし、それで学校に間に合わなくなってしまっては困ります。

課題
PCK 君がキタカタ駅に着いていなければならない時刻、アイヅ駅を発車してシオカワ駅に向かう電車の１日の発車時刻表、シオカワ駅を発車してキタカタ駅に向かう電車の１日の発車時刻表が与えられる。
このとき、PCK 君がシオカワ駅でお父さんにお弁当を渡してから、キタカタ駅に着いていなければならない時刻までに到着できるかを判定するプログラムを作成せよ。
ただし、アイヅ駅を発車してシオカワ駅に着く電車と、シオカワ駅を発車してキタカタ駅に着く電車は、どちらも到着までちょうど 10 分かかるとする。また、PCK 君がシオカワ駅で降りてお弁当を渡して乗り換えることができるまで 1 分かかるとする。

入力
入力は以下の形式で与えられる。
h m
N
a1 b1
a2 b2:
aN bN
M
c1 d1
c2 d2:

cM dM
１行目にPCK君がキタカタ駅に着いていなければならない時刻h時m分を表す２つの整数h(5≦h≦12)とm(0≦m≦59)が与えられる。
続く１行に、アイヅ駅を発車してシオカワ駅に向かう電車の本数N(1≦N≦20)が与えられる。続くN行に、アイヅ駅を発車してシオカワ駅に向かう電車の発車時刻が早い順に与えられる。ただし、同じ発車時刻が2つ以上続くことはない。アイヅ駅を発車する i 番目の電車の発車時刻は２つの整数
ai(5≦ai≦12)とbi (0≦bi≦59)からなり、ai時bi分にi番目の電車が発車することを表す。
続く１行に、シオカワ駅を発車してキタカタ駅に向かう電車の本数M(1≦M≦20)が与えられる。続くM行に、シオカワ駅を発車してキタカタ駅に向かう電車の発車時刻が早い順に与えられる。ただし、同じ発車時刻が2つ以上続くことはない。シオカワ駅を発車する i 番目の電車の発車時刻は２つの整数
ci(5≦ci≦12)とdi (0≦di≦59)からなり、ci時di分にi番目の電車が発車することを表す。

出力
PCK 君がキタカタ駅に着いていなければならない時刻までに到着することができるなら「1」を、できないなら「0」を１行に出力する。

入出力例
入力例１8 0

出力例１
135 106 107 1025 156 12
入力例２8 0
37 40
7 45
7 50
35 15
6 127 50

出力例２0問題５デジタル時計（６点）

PCK 君は夏休みの自由工作としてデジタル時計を作成しています。PCK 君が設計した時計は、下図のよ
うに、時を表す２つの数字（00～23）と分を表す２つの数字（00～59）、合計４つの数字で構成されています（図は午前３時５９分を示しています）。

１つの数字は、セグメントと呼ばれる線分７つから成り、それらを点灯・消灯させることで表示されます。各数字は下図の形式で表示されます。

PCK 君が作成したデジタル時計は、各セグメントについて、消灯の状態から点灯の状態へと変化した瞬間だけ電力１を消費しますが、それ以外は電力を消費しません。たとえば、数字 4 から数字 5 へ変化す
るときは 2 つのセグメントが新たに点灯するため、その消費電力は 2 となります。また、たとえば、時刻 09:59 から時刻 10:00 に変化した瞬間は左の数字から 0,1,2,1 の合計 4 の電力を消費します。

課題
同じ日の２つの時刻 h1:m1 と h2:m2 が与えられる。h1:m1 から h2:m2 まで時間が経過する間に消費する電力の合計を求めるプログラムを作成せよ。ただし、時や分が１桁の数のときでも１０の位には０が表示されるものとする。

入力
入力は以下の形式で与えられる。
h1 m1
h2 m2
１行目に時刻h1:m1を表す２つの整数h1とm1が与えられる。２行目に時刻h2:m2を表す２つの整数h2とm2が与えられる。ただし、0≦hi＜24、0≦mi＜60、h1×60 + m1 ＜ h2 ×60 + m2とする。

出力消費電力の合計を１行に出力する。

入出力例
入力例
9 59

出力例
4

10 1
はじめに時刻09:59から時刻10:00に変化し、次に時刻10:00から時刻10:01に変化するので、電力消費量は合計4になる。

問題６
(※

ミックススパイス１（６点）

問題６と問題７は入力データの取り得る値と時間制限だけが異なります。)

調理の際、スパイスをミックスして使用すると、１種類のスパイスだけ使用したときより風味が増します。ミックススパイスは、数種類のスパイスをあらかじめ決められた比率で混ぜ合わせた調味料です。
あなたは予算の許す範囲で数種類のスパイスを購入し、できるだけ大量のミックススパイスを作ろうとしています。あなたの手元には、既にスパイスがいくらかあります。さらに、各スパイスの購入額の合計が予算を超えない範囲でいくらでも多くスパイスを買い足すことができます。こうして集めたスパイスを使って、あなたは最大でどれだけのミックススパイスを作ることができるでしょうか。

課題
ミックススパイスに使うスパイスの種類の数と予算、各スパイスの 1 グラム当たりの価格、手元にある各スパイスの量、ミックススパイスの比率が与えられたとき、最大で何グラムのミックススパイスを作ることができるかを計算するプログラムを作成せよ。ただし、スパイスを購入する最小単位は 1 グラムとし、スパイスの調合をするときに使うことができる各スパイスの最小単位も１グラムとする。

入力
入力は以下の形式で与えられる。
N C
a1：
aN
b1：
bN
x1：
xN
１行目にスパイスの種類の数N(2≦N≦10)とミックススパイスの予算C(0≦C≦1,000)が与えられる。続
くN行に、i番目のスパイスの1グラム当たりの価格ai(1≦ai≦10)が整数で与えられる。続くN行に、手元にあるi番目のスパイスの量bi(0≦bi≦10)がグラム単位の整数で与えられる。続くN行に各スパイスの比率x1:x2:…:xNを示す数xi(1≦xi≦10)が整数で与えられる。ただし、x1,x2,…,xNの最大公約数は１であるものとする。

出力作ることのできるミックススパイスの最大の量をグラム単位で１行に出力する。

入出力例
入力例１2 100

出力例１30285511入力例２3 10010101010102243

出力例２27問題７(※ミックススパイス２（８点）

問題６と問題７は入力データの取り得る値と時間制限だけが異なります。)

調理の際、スパイスをミックスして使用すると、１種類のスパイスだけ使用したときより風味が増します。ミックススパイスは、数種類のスパイスをあらかじめ決められた比率で混ぜ合わせた調味料です。
あなたは予算の許す範囲で数種類のスパイスを購入し、できるだけ大量のミックススパイスを作ろうとしています。あなたの手元には、既にスパイスがいくらかあります。さらに、各スパイスの購入額の合計が予算を超えない範囲でいくらでも多くスパイスを買い足すことができます。こうして集めたスパイスを使って、あなたは最大でどれだけのミックススパイスを作ることができるでしょうか。

課題
ミックススパイスに使うスパイスの種類の数と予算、各スパイスの 1 グラム当たりの価格、手元にある各スパイスの量、ミックススパイスの比率が与えられたとき、最大で何グラムのミックススパイスを作ることができるかを計算するプログラムを作成せよ。ただし、スパイスを購入する最小単位は 1 グラムとし、スパイスの調合をするときに使うことができる各スパイスの最小単位も１グラムとする。

入力
入力は以下の形式で与えられる。
N C
a1：
aN
b1：
bN
x1：
xN
１行目にスパイスの種類の数N(2≦N≦100)とミックススパイスの予算C(0≦C≦1010=10の10乗)が与えられる。続くN行に、i番目のスパイスの1グラム当たりの価格ai(1≦ai≦10,000)が整数で与えられる。続
くN行に、手元にあるi番目のスパイスの量bi(0≦bi≦10,000)がグラム単位の整数で与えられる。続くN行に各スパイスの比率x1:x2:…:xNを示す数xi(1≦xi≦10,000)が与えられる。ただし、x1,x2,…,xNの最大公約数は１であるものとする。

時間制限
入力に対して、実行時間が１秒を超えてはならない。

出力作ることのできるミックススパイスの最大の量をグラム単位で１行に出力する。

入出力例
入力例１2 100

出力例１30285511入力例２3 100

出力例２2710101010102243
入力例３2 10000000000
111000010000
11

出力例３10000020000

問題８

募金街道

（１０点）

トクイチさんは、イズア地方の民のために仏像を作ることを思い立ち、その資金を集めることにしました。トクイチさんは、旅をすると寄付金がよく集まると言われている街道、通称「募金街道」を旅する計画を立てています。
募金街道は街道沿いに町が並んだ一直線の街道で、その起点の町から終点の町まで順番に１から番号が付いています。トクイチさんはまず町１に入り、町２，町３、...と順番に進んでいきます。トクイチさんはすべての町で寄付金集めができますが、以下のルールに従わなければなりません。
⚫

トクイチさんはそれぞれの町で集める寄付金の目標金額を決める。その町で目標金額まで集めたら、次の町に向かう。

⚫

ある町で集める目標金額を０円にして、その町で寄付金を集めないことも可能だが、目標金額を負の値にすることはできない。

⚫

町１での目標金額は０円か１円のどちらかとする。

⚫

町１以外の町での目標金額は、その直前の町での目標金額から１円増やした金額、１円減らした金額、同じ金額のうちのどれかでなければならない。

⚫

いくつかの町には関所があり、さらに以下のルールに従う。
➢

関所がある町では、トクイチさんはその町で集める目標金額を関所に届け出なければならない。

➢

関所ごとに定められた金額と届け出た金額が一致したときは、その町での募金活動が認められ、その先の町へも旅を続けられる。

➢

関所ごとに定められた金額と届け出た金額が一致しなければ、その町での募金活動は認められず、旅もそこで終えなければならない。

たとえば、町３に関所があり、そこで定められた金額が２円とします。このとき、町１，２，３での目標金額をそれぞれ１円、２円、２円とすれば、町３での目標金額を関所で定められた金額と一致させることができます。
トクイチさんは関所ごとに定められた金額を突き止めました。その情報を元にして、どのように目標金額を決めれば、集める寄付金の総額を最大にできるか頭を悩ませています。

課題
街道沿いの町の数と、関所がある町の番号と関所ごとに定められた金額が与えられたとき、トクイチさんが集められる寄付金の総額の最大値を計算するプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
N M
a1 b1
a2 b2
:
aM bM
１行目に街道沿いの町の数N(1≦N≦1,000,000,000)、関所の数M(1≦M≦min(N,100000))が与えられる。続くM行に関所がある町の番号ai(1≦ai≦N)とその関所で定められた金額bi(0≦bi≦1,000,000,000)が与えられる。なお、i＜jのとき、ai＜ajである。

時間制限
入力に対して、実行時間が３秒を超えてはならない。

出力
トクイチさんが集められる最大の金額を１行に出力する。

入出力例
入力例１出力例１5 13 212入力例２出力例２7 15 610入力例３出力例３5 22 24 06問題９奇数の精と偶数の精（１０点）

数が大好きなアンドウさんは、興味を持った様々な数を毎日ノートにせっせと書き取っています。奇数の守護者である奇数の精は、いたずら心を起こしてアンドウさんがノートに書いた数をすべて奇数にしてしまおうと考えました。
奇数の精が持っている魔法の消しゴムを使って、ノートに書かれた数から数字一つを選んで消すと、その数を別の数にすることができます。たとえば数 12345 からその中の数字 4 を消すと、数 1235 になります。さらに、数字 5 を消すと、数 123 になります。すべての数字が消えると、その数はノートから消えます。数字を一つ消すごとに消しゴムの長さが１減ります。消しゴムは長さが０になると使えなくなります。
奇数の精は消しゴムを使って、すべての数を奇数にしようとしています。偶数の守護者である偶数の精は、すべての数が奇数になるのを防ぐために、奇数の精が消しゴムを使う前に、自分の消しゴムでノートの数に含まれる数字をいくつか消そうとしています。
はたして、ノートに書かれている数はすべて奇数になるのでしょうか。

課題
ノートに書かれた数と、奇数の精と偶数の精が持っている消しゴムの長さが与えられる。偶数の精が最適な消し方でノートの数がすべて奇数になることを防ごうとしたとき、奇数の精がすべての数を奇数にできるかどうかを出力するプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
NX Y
a1a2：
aN
１行目にノートに書かれた数の個数N(1≦N≦100)が与えられる。続く１行に奇数の精が持っている消しゴムの長さX(1≦X≦100)と偶数の精が持っている消しゴムの長さY(1≦Y≦100)が与えられる。続くN行に、ノートに書かれたi番目の数ai(1≦ai＜10の100乗) が与えられる。
ただし、ノートに書かれた数aiの桁は1から9の文字で構成され、0を含まない。また、奇数の精と偶数の精が、消しゴムがなくなるまで文字を消しても、ノートからすべての数が消えるような入力は与えられないものとする。

時間制限
入力に対して、実行時間が３秒を超えてはならない。

出力すべての数を奇数にできるなら「Yes」、すくなくとも１つの偶数が含まれるなら「No」を出力する。

入出力例
入力例１4出力例１No4 2295428832757偶数の精が２番目の数の数字 5 と、３番目の数の数字 3 を消すことによって、奇数の精がどの数の中の４つの数字を消しても、すべての数を奇数とすることができなくなる。
入力例２24 38652147114

出力例２Yes問題１０

蜘蛛の巣上の最短経路（１０点）

PCK 君は夏休みの自由研究のために、飯森山に生息するミニグモを観察しています。ミニグモの巣は図(a)に示すように、中心から放射状に均等に並んだ N 本の線分と、これらの線分の上に頂点を持つ M 個の同心の正 N 角形の枠から構成されています。同心多角形と、そのひとつ外側にある同心多角形との間の、放射状の線分に沿って測った間隔は 1cm です。同心多角形の中心から、一番内側の同心多角形の頂点までの距離も 1cm ですが、この間に線分は存在しません。図は N = 8, M = 4 の巣を表しています。
同心多角形には中心に近い順に 1 から M までの番号 i、放射状の各線分には 0 から N-1 までの番号 j が割り振られており、同心多角形 i と放射状の線分 j の交点の座標を(i, j)で表します。

ミニグモは、巣を構成する線分を伝って交点間を移動することができ、獲物が巣にひっかかると、現在地の交点から目的地の交点まで、最短の移動距離で移動します。たとえば、図(b)は現在地(3, 3)から目的地(4, 0)への移動経路を表しています。
研究の結果、PCK 君はミニグモの特殊な能力を発見しました。ミニグモは現在地から目的地まで移動する間に、巣を構成する線分に交差しない新たな線分（上図では点線で示されている）を最大 K 本まで生成することができるのです。たとえば、図(c)は交点(1, 3)から交点(1, 0)へ 1 本の新たな線分を張った、現在地(3, 3)から目的地(4, 0)への移動経路を表します。また、図(d)は交点(2, 3)から交点(1, 2)へ張った新たな線分と、交点(1, 1)から交点(2, 0)へ張った新たな線分を含む、現在地(3, 3)から目的地(4, 0)への移動経路を表します。

課題
巣の大きさを表す情報、ミニグモの現在地と目的地、新たな線分を生成できる最大の回数が与えられる。
ミニグモが現在地から目的地へ移動するための最短の距離(cm)を求めるプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
N M K
rs psrg pg
１行目に放射状の線分の数 N(4≦N≦20)、多角形の数 M(2≦M≦20)、新たな線分を生成できる回数 K(0≦K≦10)が与えられる。２行目にミニグモの現在地の座標(rs,ps)を表す２つの整数 rs,ps(1≦rs≦M かつ0≦ps＜N)が与えられる。３行目にミニグモの目的地の座標(rg,pg)を表す２つの整数 rg,pg(1≦rg≦M かつ 0≦pg＜N)が与えられる。現在地の座標と目的地の座標は異なる(rs≠rg または ps≠pg)。

時間制限
入力に対して、実行時間が３秒を超えてはならない。

出力
最短の距離を１行に実数で出力する。ただし、誤差がプラスマイナス 0.00001 を超えてはならない。

入出力例
入力例１8 4 0

出力例１7.29610059

3 34 0
入力例２8 4 1

出力例２6.84775907

3 34 0
入力例３8 4 23 34 0

出力例３6.71261838

問題１１

決まりを守る漁師（１２点）

ケンジロウ君は湖で魚を採る漁師です。湖の全体は長方形の形をしています。湖には正方形の形に区切られた管理区画が格子状に並んでいます。地図上では湖の左上の管理区画の座標を(1,1)とし、上から i番目、左から j 番目の管理区画の座標を(i,j)としています。これまでの経験で、すべての管理区画に１匹ずつ魚がいることと、それぞれの魚の価格がわかっています。
漁は長方形の網を設置して管理区画のいくつかを網で囲うことで行います。網で囲われた管理区画の中にいる魚はすべて手に入れることができます。しかし、魚の育成を保護するためのルール導入が決まり、漁師はこのルールを守って漁を行うことになりました。ルールの詳細はまだわかりませんが、ルールの基準になるのは一度の網の設置で手に入れた魚を価格の順に並べたときに、安い方から K 番目に位置する魚の価格であることがわかっています。

ケンジロウ君は、網が設置できるすべての場所について、安い方から K 番目に位置する魚の価格を調べておくことで、少しでも早くルールに対応して漁を始められるようにしようと考えました。

課題
湖のそれぞれの区画にいる魚の価格、管理区画を囲う網の大きさ、魚の価格を調べる位置 K が与えられたときに、網が設置できるすべての場所について安い方から K 番目に位置する魚の価格を表示するプログラムを作成せよ。ただし、網は回転や変形をしない。

入力
入力は以下の形式で与えられる。
H W R CK
a1,1 a1,2 … a1,Wa2,1 a2,2 … a2,W：
aH,1 aH,2 … aH,W
１行目に、湖の縦の区画の数H(1≦H≦400)と横の区画の数W(1≦W≦400)、管理区画を囲う網の縦の区画の数R(1≦R≦H)、横の区画の数C(1≦C≦W)が与えられる。続く１行に価格を調べる位置K(1≦K≦R×C)が与えられる。続くH行に、座標(i,j)の区画にいる魚の価格ai,j(0≦ai,j≦1,000,000,000)が与えられる。

時間制限
入力に対して、実行時間が２秒を超えてはならない。

出力
出力は(H-R+1)×(W-C+1)行である。網が設置できるそれぞれの場所について求めた魚の価格を、１行にひとつずつ昇順で出力する。

入出力例
入力例
3 3 2 2

出力例2385 7 988 9 293 2 1
左上が(1,1)、右下が(2,2)の区間にいる魚の価格 5,7,8,9 の安い方から 3 番目の価格は 8 である。
左上が(1,2)、右下が(2,3)の区間にいる魚の価格 7,9,9,2 の安い方から 3 番目の価格は 9 である。
左上が(2,1)、右下が(3,2)の区間にいる魚の価格 8,9,3,2 の安い方から 3 番目の価格は 8 である。
左上が(2,2)、右下が(3,3)の区間にいる魚の価格 9,2,2,1 の安い方から 3 番目の価格は 2 である。

問題１２

回転マスゲーム（１２点）

イヅア高校の体育祭の呼び物は回転マスゲームです。このマスゲームでは、先生の号令に合わせて生徒達が回転して体の向きを変えます。生徒達が一糸乱れず動くのがカッコいいと評判です。
マスゲームに参加する N 人の生徒には、1 番から N 番まで番号が付けられています。はじめ、N 人の生徒が 1 番から N 番まで番号順に、東から西に一列に並び、全員が北を向いて立ちます。先生は、何番から何番までの生徒がどれだけ回転するか指示を出します。先生が a,b,c と３つの数を叫ぶと、a 番目から b 番目までの生徒が、c の値に応じて一斉に回転して体の向きを変えます。c は整数で、正なら生徒が左回り、負なら生徒が右回りに、数の大きさ１ごとに４分の１回転します。たとえば、1 なら左回りに４分の１回転、-2 なら右回りに半回転、4 なら左回りに 1 回転、-6 なら右回りに 1 回転半回ります。
指示を出す役目の先生は、いくつかの時点での指示の直後で、指定した範囲の番号の生徒のうち北を向いている生徒の人数から南を向いている生徒の人数を引いた値が知りたいという問い合わせを校長先生からもらいました。号令の履歴のメモは手元にあるので、プログラムを書けばどの時点でも知りたい人数が割り出せるはずです。

課題
先生の号令と校長先生からの問い合わせに関する情報が与えられたとき、各問い合わせについて北を向いている生徒の人数から南を向いている生徒の人数を引いた値を求めるプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
N M
info1
info2
:
infoM
１行目にマスゲームに参加した生徒の人数N(1≦N≦300,000)、号令と問い合わせに関する情報の数M(1≦M≦100,000)が与えられる。続くM行に号令と問い合わせに関する情報infoiが与えられる。情報は時系列順に並んでいる。各infoiは、以下のいずれかの形式で与えられる。
1 a b cまたは
2 d e
1 a b c は、a番目からb番目までの生徒が数cに応じて回転せよという号令を表す。ただし、1≦a≦b≦N、-1,000≦c≦1000である。2 d eは、その直前の号令の直後に、d番目からe番目までの生徒のうち北を向いている生徒の人数から南を向いている生徒の人数を引いた値がいくつになるかという問い合わせを表す。ただし、1≦d≦e≦Nである。
問い合わせに関する情報は１つ以上与えられる。

時間制限
入力に対して、実行時間が２秒を超えてはならない。

出力
各問い合わせについて、北を向いている生徒の人数から南を向いている生徒の人数を引いた値を 1 行に出力する。

入出力例
入力例

出力例

5 52 1 5
1 1 2 22 1 5
1 2 5 -1
2 1 551-1

問題１３通勤路（１２点）

PCK 君が住むアイヅ町には、N 個の地点と各地点をつなぐ N-1 本の道があります。地点にはそれぞれ 1 から N までの番号がついていて、どの道も双方向に移動することができます。また、どの地点からでも、いくつかの道を通っていけば他の地点に到達できます。
株式会社 IZUA の CEO である PCK 君は、日々の生活に変化を加えるため、ルーチンワークとして毎日通勤路を変えることにしています。
PCK 君は、以下の条件を満たす経路で通勤します。
•

自宅の最寄りの地点 u を出発し、会社の最寄りの地点 v へ到着する経路である。

•u と v は出発時と到着時にそれぞれちょうど 1 度通る。

•

経路上の u と v 以外の各地点は高々２回まで通る。

•

経路上の各道は高々２回まで通る。

PCK 君は自宅と会社の移転を検討していて、移転後に何通りの通勤路を楽しむことができるか知りたがっています。

課題
地点の数、地点同士を直接つなぐ道の情報、移転後の自宅の最寄りの地点 u と会社の最寄りの地点 v が与えられる。ただし、u と v の組は質問としていくつか与えられる。各質問に対して、通勤路の数を求めるプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
N
s1 t1
s2 t2:
sN-1 tN-1
Q
u1 v1
u2 v2
:
uQ vQ
１行目に地点の数 N(2≦N≦100,000)が与えられる。続く N−1 行に、２つの地点を直接つなぐ道の情報が与えられる。si と ti (1≦si＜ti≦N)は i 番目の道がつなぐ２つの地点の番号である。ただし、どの２つの地点についても、それらを直接つなぐ道は１本以下とする。続く行に質問の数 Q(1≦Q≦100,000)が与えられる。続く Q 行に各質問を表す２つの整数 ui と vi(1≦ui＜vi≦N)が与えられる。

時間制限入力に対して、実行時間が３秒を超えてはならない。

出力
質問ごとに、通勤路の数を 998,244,353 で割った余りを１行に出力する。

入出力例
入力例
4

出力例
11 222 3
2 42
1 2
1 3