Chef works as a cook in a restaurant. Each morning, he has to drive down a straight road with length K$K$ to reach the restaurant from his home. Let's describe this road using a coordinate X$X$; the position of Chef's home is X=0$X = 0$ and the position of the restaurant is X=K$X = K$.
The road has exactly two lanes (numbered 1$1$ and 2$2$), but there are N$N$ obstacles (numbered 1$1$ through N$N$) on it. For each valid i$i$, the i$i$-th obstacle blocks the lane Li$L_i$ at the position X=Xi$X = X_i$ and does not block the other lane.
When driving, Chef cannot pass through an obstacle. He can switch lanes in zero time at any integer X$X$-coordinate which does not coincide with the X$X$-coordinate of any obstacle. However, whenever he switches lanes, he cannot switch again until driving for at least D$D$ units of distance, and he can travel only in the direction of increasing X$X$. Chef can start driving in any lane he wants. He can not switch lanes at non-integer  X$X$-coordinate.
Sometimes, it is impossible to reach the restaurant without stopping at an obstacle. Find the maximum possible distance Chef can travel before he has to reach an obstacle which is in the same lane as him. If he can avoid all obstacles and reach the restaurant, the answer is K$K$.

-----Input-----
- The first line of the input contains a single integer T$T$ denoting the number of test cases. The description of T$T$ test cases follows.
- The first line of each test case contains three space-separated integers N$N$, K$K$ and D$D$.
- The second line contains N$N$ space-separated integers X1,X2,…,XN$X_1, X_2, \ldots, X_N$.
- The third line contains N$N$ space-separated integers L1,L2,…,LN$L_1, L_2, \ldots, L_N$.

-----Output-----
For each test case, print a single line containing one integer ― the maximum distance Chef can travel.

-----Constraints-----
- 1≤T≤1,000$1 \le T \le 1,000$
- 1≤N≤105$1 \le N \le 10^5$
- 2≤K≤109$2 \le K \le 10^9$
- 1≤D≤109$1 \le D \le 10^9$
- 1≤Xi≤K−1$1 \le X_i \le K-1$ for each valid i$i$
- Xi<Xi+1$X_i < X_{i+1}$ for each valid i$i$
- 1≤Li≤2$1 \le L_i \le 2$ for each valid i$i$
- the sum of N$N$ over all test cases does not exceed 106$10^6$

-----Subtasks-----
Subtask #1 (100 points): original constraints

-----Example Input-----
4
2 10 20
4 7
1 2
4 15 20
4 6 9 13
1 2 2 1
5 10 1
1 3 5 7 9
1 2 1 2 1
2 10 2
4 5
1 2

-----Example Output-----
10
13
10
5

-----Explanation-----
Example case 1: Chef can start in lane 2$2$ and switch to lane 1$1$ at the position X=6$X = 6$, then continue until reaching the restaurant.
Example case 2: Chef can start in lane 2$2$ and switch to lane 1$1$ at X=5$X = 5$. However, he cannot avoid the obstacle at X=13$X = 13$, because he has not driven for at least 20$20$ units since the last switch.
Example case 3: Chef should start in lane 2$2$ and then switch lanes at the positions X=2$X=2$, X=4$X=4$, X=6$X=6$ and X=8$X=8$. This way, he can reach the restaurant.
Example case 4: Chef can start in lane 2$2$ but he cannot escape the second obstacle at X$X$=5 since the first obstacle at X$X$=4 doesn't give enough space for Chef to switch lanes.

Difficulty: VERY_HARD
Tags: Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
for _ in range(int(input())):
	(n, k, d) = [int(x) for x in input().split()]
	x = [int(x) for x in input().split()]
	l = [int(x) - 1 for x in input().split()]
	initial_lane = 1 - l[0]
	i = 0
	while i < n and l[i] != initial_lane:
		i += 1
	if i == n:
		print(k)
		continue
	if x[i] == x[i - 1] + 1:
		print(x[i])
		continue
	lane = 1 - initial_lane
	until_switch = d
	while i < n:
		if until_switch > x[i] - 1 - (x[i - 1] + 1):
			if l[i] == lane:
				break
			else:
				until_switch -= x[i] + 1 - (x[i - 1] + 1)
				if until_switch < 0:
					until_switch = 0
				i += 1
				continue
		if lane != l[i]:
			until_switch = 0
		else:
			time = x[i - 1] + 1 + until_switch
			until_switch = d - (x[i] + 1 - time)
			if until_switch < 0:
				until_switch = 0
			lane = 1 - lane
		i += 1
	print(x[i] if i < n else k)


for _ in range(int(input())):
	(n, k, d) = [int(a) for a in input().split()]
	blocks = [int(a) for a in input().split()]
	lanes = list(map(int, input().split()))
	Flag = 0
	z = -10000000000000
	for i in range(n - 1):
		if lanes[i] != lanes[i + 1]:
			z = max(blocks[i] + 1, z + d)
			if z >= blocks[i + 1]:
				print(blocks[i + 1])
				Flag = 1
				break
	if Flag == 0:
		print(k)


for _ in range(int(input())):
	(n, k, d) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	(x, z) = (0, 0)
	if b[0] == 1:
		y = 1
	else:
		y = 2
	c = True
	for i in range(1, n):
		if y != b[i]:
			if a[i] - x <= d and z != 0 or a[i] - a[i - 1] == 1:
				c = False
				print(a[i])
				break
			if z == 0:
				z = 1
				x = a[i - 1] + 1
			else:
				x = max(a[i - 1] + 1, x + d)
			y = b[i]
	if c:
		print(k)


t = int(input())
for _ in range(t):
	(n, k, d) = map(int, input().split())
	x = list(map(int, input().split()))
	l = list(map(int, input().split()))
	lane = 3 - l[0]
	switched = -float('inf')
	ans = k
	for i in range(n):
		if l[i] == lane:
			if switched + d < x[i] and x[i - 1] + 1 < x[i]:
				lane = 3 - lane
				switched = max(x[i - 1] + 1, switched + d)
			else:
				ans = x[i]
				break
	print(ans)


def two_lane(n, k, d, l, x):
	flag = 0
	z = -10 ** 10
	for i in range(n - 1):
		if l[i] != l[i + 1]:
			z = max(x[i] + 1, z + d)
			if z >= x[i + 1]:
				return x[i + 1]
				flag = 1
				break
	return k
t = int(input())
while t:
	t -= 1
	(n, k, d) = map(int, input().split())
	x = list(map(int, input().split()))
	l = list(map(int, input().split()))
	print(two_lane(n, k, d, l, x))


def opp(n):
	if n == 1:
		return 2
	return 1

def main():
	(n, k, d) = [int(j) for j in input().split()]
	x = [int(j) for j in input().split()]
	l = [int(j) for j in input().split()]
	for i in range(n - 1):
		if l[i] != l[i + 1] and x[i + 1] != x[i] + 1:
			last_turn = x[i] + 1
			curr_lane = l[i]
			last_obs_encounter = i
			break
		elif l[i] != l[i + 1] and x[i + 1] == x[i] + 1:
			print(x[i + 1])
			return
	for j in range(last_obs_encounter, n - 1):
		if l[j + 1] == curr_lane:
			if x[j + 1] - last_turn + 1 >= d and x[i + 1] != x[i] + 1:
				curr_lane = opp(curr_lane)
				last_turn = last_turn + d
			elif l[i] != l[i + 1] and x[i + 1] == x[i] + 1:
				print(x[i + 1])
				return
			else:
				flag = False
				last_spot = x[j + 1]
				print(last_spot)
				return
				break
		else:
			pass
	print(k)
	return

def setter_main():
	(n, k, d) = [int(j) for j in input().split()]
	x = [int(j) for j in input().split()]
	l = [int(j) for j in input().split()]
	last_turn = -10 ** 10
	ans = k
	lane = opp(l[0])
	for i in range(n):
		if l[i] != lane:
			continue
		bst = max(last_turn + d, x[i - 1] + 1)
		if bst >= x[i]:
			ans = x[i]
			break
		lane = opp(lane)
		last_turn = bst
	print(ans)
for t in range(int(input())):
	setter_main()


for _t in range(int(input())):
	(n, k, d) = list(map(int, input().split()))
	xs = list(map(int, input().split()))
	ls = list(map(int, input().split()))
	my_x = 0
	my_l = 3 - ls[0]
	for (x, l_) in zip(xs, ls):
		if l_ == my_l:
			if x <= my_x:
				print(x)
				break
			my_l = 3 - my_l
			my_x = max(x + 1, my_x + d)
		else:
			my_x = max(x + 1, my_x)
	else:
		print(k)


import math
for _ in range(int(input())):
	(n, k, d) = [int(x) for x in input().split()]
	x = [int(x) for x in input().split()]
	l = [int(x) - 1 for x in input().split()]
	lane = l[0]
	switch_time = -math.inf
	i = 0
	while True:
		while i < n and l[i] == lane:
			i += 1
		if i == n:
			break
		switch_time = max(switch_time + d, x[i - 1] + 1)
		if switch_time >= x[i]:
			break
		lane = 1 - lane
	print(x[i] if i < n else k)