AT_aalc001_l 数列間の swap

You are given sequences of integers $ A=(A_1,A_2,\ldots,A_N) $ , $ B=(B_1,B_2,\ldots,B_N) $ , and $ C=(C_1,C_2,\ldots,C_N) $ , each of length $ N $ . Process $ Q $ queries. Each query is of one of the following $ 4 $ types: - `1 l r`: For every integer $ k $ satisfying $ l\leq k\leq r $ , swap $ A_k $ and $ B_k $ . - `2 l r`: For every integer $ k $ satisfying $ l\leq k\leq r $ , swap $ B_k $ and $ C_k $ . - `3 l r`: For every integer $ k $ satisfying $ l\leq k\leq r $ , swap $ C_k $ and $ A_k $ . - `4 i`: Print the smallest integer $ j $ satisfying $ i\leq j\leq N $ and $ \displaystyle\sum_{k=i}^{j}A_k\gt0 $ . If no such $ j $ exists, print $ N+1 $ .

The input is given from Standard Input in the following format: > $ N $ $ Q $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $ $ B_1 $ $ B_2 $ $ \ldots $ $ B_N $ $ C_1 $ $ C_2 $ $ \ldots $ $ C_N $ $ \mathrm{query}_1 $ $ \mathrm{query}_2 $ $ \vdots $ $ \mathrm{query}_Q $ Each query is given in one of the following formats: > $ 1 $ $ l $ $ r $ > $ 2 $ $ l $ $ r $ > $ 3 $ $ l $ $ r $ > $ 4 $ $ i $

Let $ q $ be the number of type $ 4 $ queries. Print $ q $ lines. The $ j $ -th line should contain the answer to the $ j $ -th type $ 4 $ query.

### Sample Explanation 1 For query $ 1 $ , $ A_2=-4\leq 0 $ and $ A_2+A_3=1>0 $ , so print $ 3 $ . After processing query $ 2 $ , $ A=(3,6,-3,4,1) $ . For query $ 3 $ , $ A_1=3\gt0 $ , so print $ 1 $ . ### Constraints - $ 1\leq N\leq 10^5 $ - $ 1\leq Q\leq 10^5 $ - $ -10^9\leq A_i,B_i,C_i\leq 10^9 $ - For queries of types $ 1,2,3 $ , $ 1\leq l\leq r\leq N $ - For type $ 4 $ queries, $ 1\leq i\leq N $ - All numerical values in the input are integers.