{"problem":{"name":"Large DP Table","description":{"content":"You are given integer sequences of length $N$: $A=(A_1,A_2,\\cdots,A_N)$, $B=(B_1,B_2,\\cdots,B_N)$, $X=(X_1,X_2,\\cdots,X_N)$, and $Y=(Y_1,Y_2,\\cdots,Y_N)$. Here, $A$ and $B$ satisfy the following prope","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc169_f"},"statements":[{"statement_type":"Markdown","content":"You are given integer sequences of length $N$: $A=(A_1,A_2,\\cdots,A_N)$, $B=(B_1,B_2,\\cdots,B_N)$, $X=(X_1,X_2,\\cdots,X_N)$, and $Y=(Y_1,Y_2,\\cdots,Y_N)$. Here, $A$ and $B$ satisfy the following properties:\n\n*   $A_1=1$.\n*   $B_1=2$.\n*   $(A_1,A_2,\\cdots,A_N,B_1,B_2,\\cdots,B_N)$ is a permutation of $(1,2,\\cdots,2N)$.\n\nDefine the integers $d_{i,j}$ ($1 \\leq i,j \\leq N$) as follows:\n\n*   $d_{1,1}=0$.\n*   If $(i,j) \\neq (1,1)$ and $A_i<B_j$, then $d_{i,j}=d_{i,j-1}+X_i$.\n*   If $(i,j) \\neq (1,1)$ and $A_i>B_j$, then $d_{i,j}=d_{i-1,j}+Y_j$.\n\nFind $\\sum_{1 \\leq i \\leq N}\\sum_{1 \\leq j \\leq N}d_{i,j}$, modulo $998244353$.\n\n## Constraints\n\n*   $2 \\leq N \\leq 250000$\n*   $A_1=1$\n*   $B_1=2$\n*   $(A_1,A_2,\\cdots,A_N,B_1,B_2,\\cdots,B_N)$ is a permutation of $(1,2,\\cdots,2N)$.\n*   $1 \\leq X_i \\leq 10^9$\n*   $1 \\leq Y_i \\leq 10^9$\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$\n$A_1$ $A_2$ $\\cdots$ $A_N$\n$B_1$ $B_2$ $\\cdots$ $B_N$\n$X_1$ $X_2$ $\\cdots$ $X_N$\n$Y_1$ $Y_2$ $\\cdots$ $Y_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc169_f","tags":[],"sample_group":[["2\n1 4\n2 3\n2 2\n1 3","8\n\nThe values of $d_{i,j}$ are as follows:\n\n*   $d_{1,1}=0$\n*   $d_{1,2}=d_{1,1}+X_1=0+2=2$\n*   $d_{2,1}=d_{1,1}+Y_1=0+1=1$\n*   $d_{2,2}=d_{1,2}+Y_2=2+3=5$\n\nThus, the answer is $0+2+1+5=8$."],["3\n1 3 5\n2 6 4\n1 10 100\n1000 10000 100000","108153"],["3\n1 6 5\n2 4 3\n1 10 100\n1000 10000 100000","333009"],["10\n1 17 4 7 16 18 9 3 12 6\n2 19 20 14 5 11 13 8 15 10\n744280520 249168130 239276621 320064892 910500852 164832983 245532751 198319687 715892722 967824729\n769431650 80707350 459924868 257261830 777045524 583882654 950300099 438099970 322288793 532405020","746075419"]],"created_at":"2026-03-03 11:01:14"}}