kyuridenamidaは, K2PCというレストランでバイトをしている.
彼は受付を担当しているが, 時給が810円と低いので, 時給が893円の厨房を担当したいと考えている.

厨房では, K2PCレストランの(唯一の商品であり)目玉商品であるK2PCハンバーガーを作る仕事が行われている.

ハンバーガーを1個作るには, 肉が1枚, パンが2枚, トッピング類が3個必要である.
今, 肉がa枚, パンがb枚, トッピング類がc個あるとする.
ハンバーガーをN個作るためには, それぞれの材料が残りいくつ必要か求めよ.

• 0 ≦ a ≦ 1000　今ある肉の枚数
• 0 ≦ b ≦ 2000　今あるパンの枚数
• 0 ≦ c ≦ 3000　今あるトッピング類の個数
• 0 ≦ N ≦ 1000　作りたいハンバーガーの個数

0 2 4
1

1 0 0

3 4 8
10

7 16 22

BITMANIAはK2PC社から発売されているDJシミュレーションゲームである.
BITMANIAでは, 与えられた譜面(ノートの集まり, 図1)を7つの鍵盤を押すことで音楽を演奏するゲームであり, kagamiz君はある押し方(以下, 運指と呼ぶ)でプレイする.

• kagamiz君には合計10本の指がある.
• 最初に10本の指の内の7本を, それぞれの指がどの鍵盤を押すかを1:1対応させるように決める.
• これを完全固定運指と呼ぶことにする. kagamiz君は音楽の開始から終了まで常にその運指でプレイする.

図1

kagamiz君は, ある音楽をノーミスでクリアできるか確かめたくなった.
kagamiz君のそれぞれの指には, それぞれ縦連耐性というものがある.
縦連耐性とは, 連続(隙間無く)落下してくるノートを最大何連続まで耐えられるかという指標である. もしその回数を超えてしまうと, 耐えられなくなり, ミスしてしまう.

あなたの仕事は, ゲーム中のある音楽の譜面データが与えられるので, 運指を工夫した場合にクリアできるか確かめることである.
kagamiz君は非常に優秀なプレイヤーなので, 縦連耐性以外のどんな要素によるミスも引き起こさない.
また, 運指は10本の指の内, 7本が, それぞれの鍵盤に1:1対応しているならどんなものでも構わない.

• 1 ≦ N ≦ 100　音楽の譜面データの縦の長さ
• 1 ≦ a_i ≦ 100　a_iはi番目の指の縦連耐性
• 譜面を表す記号はXまたは-のいずれかである.
• 譜面データは, 最後に落ちてくるノートから与えられることに注意せよ.

13
1 1 2 1 1 1 1 1 1 3
-X--X-X
-------
X--X-X-
--X-X--
XX-----
--X-X--
X----X-
--X----
--X----
-------
--X----
--X----
X-XX-X-

YES

2
1 1 1 1 2 2 2 3 3 3
XXXXXXX
XXXXXXX

NO

この譜面をクリアするには, 縦連耐性が2以上の指を7本選ばなければならない.
しかし, 縦連耐性が2以上の指は6本しかないのでkagamiz君はこの譜面をノーミスクリアすることが出来ない.

kagamizは, 紅茶を飲みながら, 次のような問題を解いていた.

"2 つの正の整数の組を次のように並べるとき, (m, n)は何番目にあるか.
(1, 1), (2, 1), (1, 2), (3, 1), (2, 2), (1, 3), (4, 1), (3, 2), (2, 3), (1, 4), (5, 1), ..."

この問題は彼には簡単すぎたので, 彼はこの問題を基に次のような問題を考えた.

"上の様な整数の組で, i 番目の組の成分と j 番目の組の成分をそれぞれ足した組は何番目にあるか.
すなわち, 上記の整数の組のi 番目を(a_i, b_i), j番目を(a_j, b_j)と表すとき, (a_i+a_j, b_i+b_j) は何番目にあるか."

あなたの仕事は, kagamizから出題されたこの問題を解くことである.

• 1 ≦ i, j ≦ 10^8　整数の組の番号
• i=j となることがある.

1 1

5

3 2

13

114 514

1155

kyuridenamidaは, お菓子を食べ過ぎて1本の歯を虫歯にしてしまった.
その歯がとても痛むので歯医者さんに治療してもらったところ, 歯の神経のうち N 箇所を治療してもらえた.

kyuridenamidaの歯の神経は, 図1に示すように, 深さがKの完全二分木になっている.
(二分木については, Wikipediaのページなどを参照せよ.)

図 1

彼の神経を表す二分木で, 深さが i で左から j 番目の神経を (i,j)と表す(図 2 ).
このとき, 根に当たる神経 (0,1) に, 先祖を遡ってたどり着ける神経を, 虫歯神経と呼ぶこととする.
ただし, 虫歯神経の先祖が既に治療されている場合, その虫歯神経は根の神経 (0, 1) に辿りつけない.
また, (0, 1)自身が治療されていなければ, (0, 1) が自身にたどり着けるものとする.

図 2

根に辿り着ける虫歯神経の個数の総和を歯の痛みとする.
あなたの仕事は, kyuridenamidaの虫歯の情報が与えらるので, その歯の痛みをkyuridenamidaに教えて上げることである.

• 1 ≦ K ≦ 50　歯の神経の深さ
• 0 ≦ N ≦ 10^5　治療済みの神経の個数
• 0 ≦ p_i ≦ K 　治療済み神経 i の深さ
• 1 ≦ q_i ≦ 2^{p_i}　治療済み神経 i の, 深さ p_iでの位置
• p_i = p_j であれば, q_i ≠ q_jが保証されている.

配点の 40% 分については, N ≦ 1000 を満たす.

1
1
1 1

2

9
0

1023

3
2
1 2
3 7

8

2 以上 n 以下の正整数 x に対して, 以下の操作が許されている.

• x+1 がn 以下のとき, x + 1 を新たな x とする.
• \sqrt{x} が整数のとき, \sqrt{x} を新たな x とする.

例えば, x = 2 のとき, 3を新しい x とすることができる.
x = 4 のとき, (2,5) のいずれかを新しい x とすることができる.

そこで, kagamizは x=2 として開始し, この操作で許される全ての遷移の仕方を, 少なくともそれぞれ 1 回ずつ以上行って 再び x=2 に戻ってくるような方法のうち, 操作回数が最小になる場合にかかる操作回数を知りたい.
あなたの仕事は, そのような方法が存在するかどうかと, 存在するならばその最小操作回数をkagamizに教えてあげることである.

• 2 ≦n ≦ 10^{12}　たどり着ける数の上限値

9

10

5

-1

4

3