佳佳有一个n*m的带权矩阵，她想从(1,1)出发走到(n,m)且只能往右往下移动，她能得到的娱乐值为所经过的位置的权的总和。

有一天，她被下了恶毒的诅咒，这个诅咒的作用是将她的娱乐值变为对p取模后的值，这让佳佳十分的不开心，因为她无法找到一条能使她得到最大娱乐值的路径了！

她发现这个问题实在是太困难了，既然这样，那就只在3*n的矩阵内进行游戏吧！

现在的问题是，在一个3*n的带权矩阵中，从(1,1)走到(3,n)，只能往右往下移动，问在模p意义下的移动过程中的权总和最大是多少。

样例解释：
移动的方案为“下下右”。

输入
单组测试数据
第一行两个数n(1<=n<=100000),p(1<=p<=1000000000)。
接下来3行，每行n个数，第i行第j列表示a[i][j]表示该点的权(0<=a[i][j]<p)。
输出
一个整数表示答案。
输入样例
2 3
2 2
2 2
0 1
输出样例
2

很容易看出来 整条路径分成三行 只有两个拐点

路径中是有三条线段的 我们可以统计每一行的前缀和

所以我们有下面的计算公式 sum[1][x]+sum[2][y]-sum[2][x-1]+sum[3][n]-sum[3][y-1]
把上述式子换一下位置 sum[1][x]-sum[2][x-1] + sum[2][y]+sum[3][n]-sum[3][y-1]
所以 我们可以想到来枚举 x 和 y 寻找最长路径 从图中可以看出 两个拐点的关系 x<=y 这个很重要
考虑枚举x，那么问题转化为询问在一堆数中求一个数k使得v(=a[x]+S[3][n])+k mod p最大

分两种情况考虑，第一种v+k∈[v,mod−1]，那么k∈[0,mod−k−1]，并且k越大越好

第二种不如第一种好，但有可能不得不选，v+k∈[1,v−1]，同样时k越大越好

也就是说，需要一种支持插入，查询前驱和最大值的数据结构，set就可以

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
int a[maxn], b[maxn];
int sum[4][maxn];
int n, mod, x;
set<int> st;
set<int> ::iterator it;
int main() {
	scanf("%d%d", &n, &mod);
	for (int i = 1; i <= 3; i++) {
		for (int j = 1; j <= n; j++) {
			scanf("%d", &x); 
			sum[i][j] = (sum[i][j - 1] + x) % mod;
		}
	}
	for (int i = 1; i <= n; i++) {
		a[i] = ((sum[1][i] - sum[2][i - 1]) % mod + mod) % mod;
		b[i] = ((sum[2][i] - sum[3][i - 1]) % mod + mod) % mod;
	}
	int res = sum[3][n];
	int ans = 0;
	st.insert(-1);
	for (int i = n; i >= 1; i--) {
		st.insert(b[i]);
		int tmp = (res + a[i]) % mod;
		x = ((mod - tmp - 1) % mod + mod) % mod;
		it = st.lower_bound(x);
		ans = max(ans, (tmp + *(--st.end())) % mod);
		ans = max(ans, (tmp + *it) % mod);
		it--;
		if (*it != -1) {
			ans = max(ans, (tmp + *it) % mod);
		}

	}
	printf("%d\n", ans);
	return 0;
}