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