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

※20:22現在, セット採点がうまく動作していないようです。修正後リジャッジを行います。(恐らくテストケース毎に表示されている結果は正しいです)

※20:35セット採点データを修正し、リジャッジを行いました。正解しているように見えた解答も不正解扱いになっている可能性があります。ご確認ください。ご迷惑をおかけしました。
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

※20:31現在, この問題もセット採点がうまく動作していないようです。修正後リジャッジを行います。(恐らくテストケース毎に表示されている結果は正しいです)。ご迷惑をおかけします。

※20:35セット採点データを修正し、リジャッジを行いました。正解しているように見えた解答も不正解扱いになっている可能性があります。ご確認ください。ご迷惑をおかけしました。

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

kagamizは, ペットのミズゴロウと毎日家から K m 離れた公園まで散歩をしている.
このとき, kagamizは往路と復路で, ミズゴロウと次のようなゲームをする:

• 1 m 先か 2 m 先にマシュマロを投げ, ミズゴロウがそのマシュマロをキャッチする.
• 投げた先にkagamizも移動し, 同じ操作を繰り返す.

ただし, このときに, 公園より後の地点や, 家より前の地点にマシュマロを投げることは許されない.
また, 往路でのスタート地点は 家から 0 mの地点, 復路でのスタート地点は 家から K mの地点であり, ここには必ず訪れることとなる.
しかし, 往路のうち P 個の地点, 復路のうち Q 個の地点, 合計 R 個の地点には水たまりがあり, せっかくのマシュマロが濡れてしまい, ミズゴロウが水たまりで遊ぶためそこから動かなくなってしまう.
したがって, 水たまりがある地点にマシュマロを投げることはしない.

このとき, kagamizとミズゴロウが, 全ての地点にマシュマロを投げ散歩をする方法は何通りあるだろうか.

あなたの仕事は, K , R , および水たまりができる地点の情報が与えられるとき, K m ある地点すべてにマシュマロを投げて, 散歩をする方法の数を 100000 で割ったあまりを kagamizに教えてあげることである.

• 1 ≦ K ≦ 3000000　家から公園までの距離
• 0 ≦ R ≦ 100000　往路または復路にある水たまりの個数の総数
• 1 ≦ a_i ≦ K 　家から水たまりがある地点までの距離
• 往路か復路を表す整数 t_i は, 必ず 1,2 のいずれかである.

配点の 30% 分については, R = 0 を満たす.
配点の 20% 分については, K ≦ 15 を満たす.
配点の 10% 分については, これら 2 つの条件を両方満たす.
配点の 40% 分については, これら 2 つの条件の少なくとも一方を満たす.
※30%+20%+10%+40%=100%という意味ではないことに注意せよ.

3 0

7

14 2
1 9
2 3

7105

1 1
2 1

0

3 2
1 1
2 1

0

kagamizは, ハッシュについて勉強をしている.
kagamizはローリングハッシュについて蟻本で学び, ハッシングが文字列探索に有効な手法だということを知った.

そこで, kagamizは, 任意の多重集合についてハッシングすることが出来ないかということを考え, 以下のようなハッシュ関数を考案した.

「
Pを素数とする. ハッシュ化する列を {x_1,x_2,x_3,...,x_n} とし, 全ての x_iについて, j≦iかつ x_j=x_iが成り立つような jの個数をC_iとすると,
(ハッシュ値) = Σx_i^{C_i} mod P
」

このハッシュ関数は容易に衝突ケースが作れてしまうが, ともかくこの関数を用いた以下の問題をあなたに解かせることにした.

問題： 長さNの数列{a_1,a_2,a_3,...,a_N} がある. この数列の Q 個の部分列について, それぞれ前述のハッシュ値を求めなさい.

• 1 ≦ N ≦ 10^5　数列の長さ
• 1 ≦ Q ≦ 10^5　ハッシュ値を求めたい連続した部分列の個数
• 1 ≦ P ≦ 10^9　ハッシュ関数で用いる素数
• 1 ≦ a_i ≦ 10^6　数列の各項の値
• 1 ≦ s_i ≦ t_i ≦ N 　各部分列の端点

配点の 20% 分については, i≠jのときa_i≠a_j を満たす.

10 10 8999
2 1 1 2 1 2 1 2 1 2
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10

2
3
4
8
9
17
18
34
35
67