AT_ajo2025_final_c Even Subgrid

$ 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 $ 進数として出力してください．

入力は以下の形式で標準入力から与えられる． > $ L $ $ N $ $ M $ $ A_1 $ $ B_1 $ $ C_1 $ $ D_1 $ $ A_2 $ $ B_2 $ $ C_2 $ $ D_2 $ $ \vdots $ $ A_N $ $ B_N $ $ C_N $ $ D_N $ $ X_1 $ $ Y_1 $ $ V_1 $ $ X_2 $ $ Y_2 $ $ V_2 $ $ \vdots $ $ X_M $ $ Y_M $ $ V_M $

答えを $ M $ 桁の $ 2 $ 進数として出力せよ．

### Sample Explanation 1 こだわり $ 1,2,3 $ を満たすことはできますが，その場合こだわり $ 4 $ は満たせません． ### Constraints - $ 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 $ - 入力はすべて整数