問題文

深さ$d$である完全二分木が与えられます。
ここで、完全二分木とは全ての頂点が「葉である」または「2つの子を持つ」をみたす木であり、かつ全ての葉の深さが同じであるようなものを指します。
また、根の深さを$1$とし、葉の深さを$d$とします。
さらに、深さが$i$で左から$j$番目である頂点に対して位置を$2^{i-1}+j-1$で定義し、 位置が$x$である頂点のことを頂点$x$と呼ぶことにします。

この木にある$2^d-1$個の頂点に対して$1$から$2^d-1$の異なる番号を1つずつ書き込むことを考えます。
このとき、以下の条件を満たすようにします。

• すべての$i,\ j$について、頂点$i$の深さが頂点$j$の深さよりも大きいならば、 頂点$i$に書き込まれる番号は頂点$j$に書き込まれる番号より大きい
• $l$が書き込まれた頂点と$r$が書き込まれた頂点を結ぶパスに含まれる辺の本数は$k$本である。
　　

入力

$d\ l\ r\ k$

入力は全て整数である
$2 \le d \le 20$
$1 \le l < r \le 2^d-1$
$1 \le k \le 10^5$

出力

答えを1行で出力してください。最後に改行してください。

サンプル

2 1 2 1

2

2 2 3 2

2

3 4 5 4

32

4 3 6 2

0

17 34 45 4

8695321