問題文

L \times L の盤面があります． 上から i 行目，左から j 列目のマスをマス (i,j) と呼ぶことにします．

最初すべてのマスは白色でしたが，すぬけくんが以下の操作を N 回行い，いくつかのマスを黒く塗りました．

• 操作 i (1 \leq i \leq N): 長方形領域 [A_i,B_i] \times [C_i,D_i] を黒く塗る． より正確に言えば，すべてのマス (r,c) (A_i \leq r \leq B_i, C_i \leq c \leq D_i) に対して，その色を黒にする．

今から，各白マスに 0 or 1 を書き込みます． ただし，書き込み方は以下の条件を満たす必要があります．

• 任意の 2 \times 2 領域について，その 4 マスがすべて白色なら，そこに書かれた値の合計は偶数である．

ところで，すぬけくんには M 個のこだわりがあります． i 番目のこだわりは，マス (X_i,Y_i) に書き込む数は V_i であってほしいというものです． こだわり i が満たされると，すぬけくんは 2^{M-i} の嬉しさを得ます．

すぬけくんが得られる嬉しさの合計の最大値を求めてください． なお，答えは M 桁の 2 進数として出力してください．

制約

• 1 \leq L \leq 10^9
• 0 \leq N \leq 250
• 1 \leq M \leq 10^5
• 1 \leq A_i \leq B_i \leq L
• 1 \leq C_i \leq D_i \leq L
• 1 \leq X_i,Y_i \leq L
• マス (X_i,Y_i) は白色である
• V_i = 0 or 1
• 入力はすべて整数

入力例 1

3 0 4
1 1 0
1 3 0
3 1 0
3 3 1

出力例 1

1110

こだわり 1,2,3 を満たすことはできますが，その場合こだわり 4 は満たせません．

入力例 2

3 1 4
2 2 2 2
1 1 0
1 3 0
3 1 0
3 3 1

出力例 2

1111

入力例 3

8 3 20
2 2 1 6
2 2 3 5
1 2 6 6
4 3 1
5 8 0
3 5 0
1 5 1
1 8 0
2 8 1
3 3 0
3 3 1
6 7 1
6 1 0
1 7 0
5 1 0
5 2 0
4 8 0
7 3 1
3 8 1
4 1 0
6 5 0
1 8 0
8 6 0

出力例 3

11111110111011110111

入力例 4

15 5 20
5 12 5 7
2 15 6 6
7 14 12 12
8 11 11 14
6 14 7 7
15 15 1
4 10 0
6 9 0
5 2 1
5 10 1
2 10 0
6 3 1
12 3 0
11 10 1
9 3 1
5 9 0
2 2 1
9 10 0
12 2 0
5 15 1
9 8 0
9 2 0
5 3 1
6 10 0
2 9 0

出力例 4

11111111111111110100