An array is beautiful if both of the following two conditions meet:

there are at least $l_1$ and at most $r_1$ elements in the array equal to its minimum;

there are at least $l_2$ and at most $r_2$ elements in the array equal to its maximum.

For example, the array $[2, 3, 2, 4, 4, 3, 2]$ has $3$ elements equal to its minimum ($1$-st, $3$-rd and $7$-th) and $2$ elements equal to its maximum ($4$-th and $5$-th).

Another example: the array $[42, 42, 42]$ has $3$ elements equal to its minimum and $3$ elements equal to its maximum.

Your task is to calculate the minimum possible number of elements in a beautiful array.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 5000$) — the number of test cases.

Each test case consists of one line containing four integers $l_1$, $r_1$, $l_2$ and $r_2$ ($1 \le l_1 \le r_1 \le 50$; $1 \le l_2 \le r_2 \le 50$).


-----Output-----

For each test case, print one integer — the minimum possible number of elements in a beautiful array.


-----Examples-----

Input
7
3 5 4 6
5 8 5 5
3 3 10 12
1 5 3 3
1 1 2 2
2 2 1 1
6 6 6 6
Output
4
5
13
3
3
3
6


-----Note-----

Optimal arrays in the test cases of the example:

$[1, 1, 1, 1]$, it has $4$ minimums and $4$ maximums;

$[4, 4, 4, 4, 4]$, it has $5$ minimums and $5$ maximums;

$[1, 2, 1, 2, 2, 1, 2, 2, 2, 2, 2, 2, 2]$, it has $3$ minimums and $10$ maximums;

$[8, 8, 8]$, it has $3$ minimums and $3$ maximums;

$[4, 6, 6]$, it has $1$ minimum and $2$ maximums;

$[3, 4, 3]$, it has $2$ minimums and $1$ maximum;

$[5, 5, 5, 5, 5, 5]$, it has $6$ minimums and $6$ maximums.

Source: codeforces | Difficulty: EASY
Tags: Mathematics

Complete search


Solutions:
import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(l1, r1, l2, r2) = map(int, input().split())
	if max(l1, l2) <= min(r1, r2):
		print(max(l1, l2))
	else:
		print(l1 + l2)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(a, b, c, d) = map(int, input().split())
	if a > c:
		(a, b, c, d) = (c, d, a, b)
	if b >= c:
		print(max(a, c))
	else:
		print(a + c)


import sys

def solve():
	inp = sys.stdin.readline
	(l1, r1, l2, r2) = map(int, inp().split())
	r = l1 + l2
	if max(l1, l2) <= min(r1, r2):
		r = min(r, max(l1, l2))
	print(r)

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


import sys
input = sys.stdin.readline
T = int(input())
for testcase in range(T):
	(l1, r1, l2, r2) = list(map(int, input().split()))
	a = max(l1, l2)
	if a <= min(r1, r2):
		print(a)
	else:
		a = l1 + l2
		print(a)


n = int(input())
l2 = []
for i in range(n):
	l = [int(x) for x in input().split()]
	l2.append(l)
for i in l2:
	if i[0] > i[2]:
		c = i[0]
	else:
		c = i[2]
	if c > i[1]:
		c = c + i[0]
	elif c > i[3]:
		c = c + i[2]
	print(c)


t = int(input())
l = []
o = []
for s in range(t):
	l = list(map(int, input().split()))
	if l[2] <= l[1] and l[0] <= l[3]:
		a = max(l[0], l[2])
	else:
		a = l[0] + l[2]
	o.append(a)
for i in range(int(t)):
	print(o[i])


for s in [*open(0)][1:]:
	a = (*map(int, s.split()),)
	((a, b), (c, d)) = sorted(zip(a[::2], a[1::2]))
	print(c + a * (c > b))


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(l1, r1, l2, r2) = list(map(int, input().split()))
	if l1 >= l2 and l1 <= r2:
		print(l1)
	elif l2 >= l1 and l2 <= r1:
		print(l2)
	else:
		print(l1 + l2)


nums = int(input())
pre = [0] * nums
for i in range(nums):
	pre[i] = list(map(int, input().split()))
for lst in pre:
	l1 = lst[0]
	r1 = lst[1]
	l2 = lst[2]
	r2 = lst[3]
	if l1 <= l2 <= r1:
		print(l2)
	elif l2 <= l1 <= r2:
		print(l1)
	else:
		print(l1 + l2)


import sys

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_ls():
	return list(map(int, sys.stdin.readline().strip().split()))

def main():
	for _ in range(int(input())):
		(a, b, c, d) = get_ints()
		if a == d:
			print(a)
		elif a <= c <= b:
			print(c)
		elif a < c and b < c:
			print(a + c)
		elif a > c and b > c:
			if c < d and a < d:
				print(a)
			elif c < d and a > d:
				print(a + c)
			else:
				print(a + c)
main()


for s in [*open(0)][1::1]:
	(a, b, c, d) = map(int, s.split())
	print([max(a, c), a + c][a > d or c > b])


a = int(input())
b = list()
for i in range(a):
	inp = list(map(int, input().split()))
	if inp[0] == inp[2]:
		b.append(inp[0])
	elif inp[0] > inp[2]:
		if inp[3] >= inp[0]:
			b.append(inp[0])
		else:
			c = inp[0] + inp[2]
			b.append(c)
	elif inp[1] >= inp[2]:
		b.append(inp[2])
	else:
		c = inp[0] + inp[2]
		b.append(c)
for j in b:
	print(j)


n = int(input())
answer = []
for _ in range(n):
	(l1, r1, l2, r2) = map(int, input().split())
	if l2 in range(l1, r1 + 1) and l1 in range(l2, r2 + 1):
		answer.append(min(l1, l2))
	elif l1 in range(l2, r2 + 1):
		answer.append(l1)
	elif l2 in range(l1, r1 + 1):
		answer.append(l2)
	else:
		answer.append(l1 + l2)
for elem in answer:
	print(elem)


import sys
n = int(sys.stdin.readline())
for i in range(n):
	(l1, r1, l2, r2) = map(int, sys.stdin.readline().split())
	if r1 >= l2 >= l1:
		result = l2
	elif r2 >= l1 >= l2:
		result = l1
	else:
		result = l1 + l2
	print(result)


import sys
n = int(sys.stdin.readline())
for i in range(n):
	[l1, r1, l2, r2] = [int(n) for n in sys.stdin.readline().strip().split()]
	if r1 < l2 or r2 < l1:
		print(l1 + l2)
	else:
		print(max(l1, l2))


import sys
input = sys.stdin.readline

def solve():
	(l1, r1, l2, r2) = map(int, input().split())
	if r1 < l2 or r2 < l1:
		return l1 + l2
	else:
		return max(l1, l2)
for _ in range(int(input())):
	print(solve())


import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T):
	(l1, r1, l2, r2) = map(int, input().split())
	if l1 > l2:
		(l1, r1, l2, r2) = (l2, r2, l1, r1)
	ans = l2
	if l2 > r1:
		ans += l1
	print(ans)


n = int(input())
l = []
for i in range(n):
	(a, b, c, d) = input().split()
	l1 = int(a)
	r1 = int(b)
	l2 = int(c)
	r2 = int(d)
	if l1 <= l2 <= r1:
		l.append(l2)
	elif l2 <= l1 <= r2:
		l.append(l1)
	else:
		l.append(l2 + l1)
for i in l:
	print(i)


lines = []
while True:
	try:
		a = input()
		lines.append(a)
	except:
		break
notest = int(lines[0])
for i in range(1, notest + 1):
	l1 = int(lines[i].split()[0])
	r1 = int(lines[i].split()[1])
	l2 = int(lines[i].split()[2])
	r2 = int(lines[i].split()[3])
	if l1 <= r2 and l1 >= l2:
		print(l1)
	elif l2 <= r1 and l2 >= l1:
		print(l2)
	else:
		print(l1 + l2)


t = input()
end_result = ''
for i in range(int(t)):
	(l1, l2, r1, r2) = input().split()
	if int(l2) < int(r1) or int(r2) < int(l1):
		end_result += str(int(l1) + int(r1)) + '\n'
	else:
		end_result += str(max(int(l1), int(r1))) + '\n'
print(end_result[:-1])


N = int(input())
inputs = []
for i in range(N):
	inputs.append(list(map(int, input().split())))
for x in inputs:
	l1 = x[0]
	r1 = x[1]
	l2 = x[2]
	r2 = x[3]
	if l2 >= l1 and l2 <= r1:
		print(l2)
		continue
	if l1 >= l2 and l1 <= r2:
		print(l1)
		continue
	print(l1 + l2)


n = int(input())
test = []
sum = []
for i in range(n):
	test.append(list(map(int, input().split())))
for i in range(n):
	if test[i][0] <= test[i][2] and test[i][2] <= test[i][1]:
		sum.append(test[i][2])
	elif test[i][2] > test[i][1]:
		sum.append(test[i][0] + test[i][2])
	elif test[i][0] > test[i][3]:
		sum.append(test[i][0] + test[i][2])
	elif test[i][2] <= test[i][0] and test[i][0] <= test[i][3]:
		sum.append(test[i][0])
for i in sum:
	print(i)


import sys
input = sys.stdin.readline
n = int(input())
for _ in range(n):
	(l1, r1, l2, r2) = [int(i) for i in input().split()]
	if l1 <= l2 and r1 >= l2:
		print(min(r1, l2))
	elif l2 <= l1 and r2 >= l1:
		print(min(r2, l1))
	else:
		print(l1 + l2)


test = input('')
min_1 = [''] * int(test)
max_1 = [''] * int(test)
min_2 = [''] * int(test)
max_2 = [''] * int(test)
sol = [0] * int(test)
for n in range(int(test)):
	(min_1[n], max_1[n], min_2[n], max_2[n]) = input('').split()
x = [0] * int(test)
for k in range(int(test)):
	if int(min_1[k]) > int(min_2[k]):
		x[k] = int(min_1[k])
		if x[k] <= int(max_2[k]):
			sol[k] = x[k]
		else:
			sol[k] = int(min_1[k]) + int(min_2[k])
	elif int(min_1[k]) < int(min_2[k]):
		x[k] = int(min_2[k])
		if x[k] <= int(max_1[k]):
			sol[k] = x[k]
		else:
			sol[k] = int(min_1[k]) + int(min_2[k])
	else:
		x[k] = int(min_1[k])
		if x[k] <= int(max_2[k]):
			sol[k] = x[k]
		elif x[k] <= int(max_1[k]):
			sol[k] = x[k]
		else:
			sol[k] = int(min_1[k]) + int(min_2[k])
for p in sol:
	print(p)


from sys import stdin

def main():
	n = int(stdin.readline().strip())
	for i in range(n):
		chain = stdin.readline().strip().split()
		(l1, r1) = (int(chain[0]), int(chain[1]))
		(l2, r2) = (int(chain[2]), int(chain[3]))
		M = max(l1, l2)
		if M <= r1 and M <= r2:
			print(M)
		else:
			m = min(l1, l2) + M
			print(m)
main()


def process(l):
	l1 = int(l[0])
	r1 = int(l[1])
	l2 = int(l[2])
	r2 = int(l[3])
	del l
	if l2 > r1 or l1 > r2:
		return l1 + l2
	elif l2 <= r1 and l1 <= l2:
		return l2
	elif l1 <= r2 and l2 <= l1:
		return l1
	else:
		return l1 + l2
n = int(input())
a = []
for i in range(1, n + 1):
	a.append(process(input().split(' ')))
for i in range(0, len(a)):
	print(a[i])


for _ in range(int(input())):
	(l1, r1, l2, r2) = list(map(int, input().split()))
	a = max(l1, l2)
	if a <= r1 and a <= r2:
		print(a)
	else:
		print(l1 + l2)


n = int(input())
a = [0 for i in range(n)]
for i in range(n):
	a[i] = [0 for ii in range(4)]
	a[i] = list(map(int, input().split()))
for i in range(n):
	if a[i][1] < a[i][2] or a[i][3] < a[i][0]:
		print(a[i][0] + a[i][2])
	else:
		print(max(a[i][0], a[i][2]))


import sys
input = sys.stdin.readline

def solve():
	(a, b, c, d) = map(int, input().split())
	if a <= d:
		if d <= b:
			if c <= a:
				return a
			else:
				return c
		elif c <= a:
			return a
		elif c <= b:
			return c
		else:
			return a + c
	return a + c
for __ in range(int(input())):
	print(solve())


def beautiful_array(l1, r1, l2, r2):
	return min(r1 - l1 + 1, r2 - l2 + 1)

def main():
	t = int(input())
	for _ in range(t):
		(l1, r1, l2, r2) = map(int, input().split())
		if l1 >= l2 and l1 <= r2:
			print(l1)
		elif l2 >= l1 and l2 <= r1:
			print(l2)
		else:
			print(l1 + l2)
main()


for _ in range(int(input())):
	(l1, r1, l2, r2) = map(int, input().split())
	if l2 > r1 or l1 > r2:
		print(l1 + l2)
	else:
		print(max(l1, l2))


t = int(input())
for i in range(t):
	(l1, r1, l2, r2) = map(int, input().split())
	if max(l1, l2) <= min(r1, r2):
		print(max(l1, l2))
	else:
		print(l1 + l2)


piBo = int(input())
s = ''
for i in range(piBo):
	(l1, r1, l2, r2) = map(int, input().split())
	if r1 >= l2 and l1 <= l2 or (r2 >= l1 and l2 <= l1):
		print(max(l1, l2))
	else:
		print(l1 + l2)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	a = [int(i) for i in input().split()]
	(l1, r1, l2, r2) = (a[0], a[1], a[2], a[3])
	if l2 <= l1 <= r2 or l1 <= l2 <= r1:
		print(max(l1, l2))
	else:
		print(l1 + l2)


for i in range(int(input())):
	(a, b, c, d) = map(int, input().split())
	if a == c or (a > c and a <= d):
		print(a)
	elif c > a and c <= b:
		print(c)
	else:
		print(a + c)


a = int(input())
for i in range(a):
	(b, c, d, e) = map(int, input().split())
	if d > c or b > e:
		print(b + d)
	else:
		print(max(b, d))


t = int(input())
for _ in range(t):
	(l1, r1, l2, r2) = map(int, input().split())
	if l1 <= l2 and l2 <= r1:
		print(l2)
	elif l2 <= l1 and l1 <= r2:
		print(l1)
	else:
		print(l1 + l2)


def main():
	import sys
	input = sys.stdin.readline
	for _ in range(int(input())):
		(l1, r1, l2, r2) = map(int, input().split())
		s1 = set(range(l1, r1 + 1))
		s2 = set(range(l2, r2 + 1))
		s3 = s1.intersection(s2)
		if s3:
			print(min(s3))
		else:
			print(l1 + l2)
main()


def main():
	import sys
	input = sys.stdin.readline
	for _ in range(int(input())):
		(l2, r2, l1, r1) = map(int, input().split())
		x1 = set(range(l2, r2 + 1))
		x2 = set(range(l1, r1 + 1))
		s = x2.intersection(x1)
		if s:
			print(min(s))
		else:
			print(l2 + l1)
main()


n = int(input())
m = []
for i in range(0, n):
	a = list(map(int, input().strip().split()))[:4]
	l1 = a[0]
	r1 = a[1]
	l2 = a[2]
	r2 = a[3]
	c = 0
	for i in range(l1, r1 + 1):
		if i >= l2 and i <= r2:
			m.append(max(l1, l2))
			c = 1
			break
	if c == 0:
		m.append(l1 + l2)
for i in m:
	print(i)


t = int(input())
ans = []
for x in range(t):
	inp = list(map(int, input().split()))
	(l1, r1, l2, r2) = (inp[0], inp[1], inp[2], inp[3])
	if l2 >= l1 and l2 <= r1 or (l1 >= l2 and l1 <= r2):
		ans.append(max(l2, l1))
	else:
		ans.append(l1 + l2)
for a in ans:
	print(a)


def inputs(lines, example=None):
	if example:
		test = []
		for t in range(int(example[0])):
			line = []
			for i in example[1 + lines * t:1 + lines * t + lines]:
				line.extend(i.split())
			test.append(line)
		return test
	else:
		test = []
		for t in range(int(input())):
			line = []
			for i in range(lines):
				line.extend(input().split())
			test.append(line)
		return test
test = inputs(1)
for i in test:
	(l1, r1, l2, r2) = (int(i[0]), int(i[1]), int(i[2]), int(i[3]))
	if l1 <= l2 and r1 >= l2:
		print(l2)
	elif l2 <= l1 and r2 >= l1:
		print(l1)
	else:
		print(l1 + l2)


import math
t = int(input())
while t:
	t -= 1
	(h, i, j, k) = input().split()
	a = int(h)
	b = int(i)
	c = int(j)
	d = int(k)
	if b < c or d < a:
		print(a + c)
	else:
		print(max(a, c))


for _ in range(int(input())):
	(l1, r1, l2, r2) = map(int, input().split())
	if l1 <= l2:
		if r1 < l2:
			re = l1 + l2
		else:
			re = l2
	elif l2 <= l1:
		if r2 < l1:
			re = l1 + l2
		else:
			re = l1
	print(re)


for i in range(int(input())):
	(l1, r1, l2, r2) = map(int, input().split())
	if r1 >= l2 >= l1:
		print(l2)
	elif l2 < l1:
		if r2 < l1:
			print(l1 + l2)
		else:
			print(l1)
	else:
		print(l1 + l2)


inp1 = int(input())
for i in range(inp1):
	(l1, r1, l2, r2) = list(map(int, input().split()))
	if l1 == r2:
		print(l1)
	elif l2 >= l1 and l2 <= r1:
		print(l2)
	elif l1 >= l2 and l1 <= r2:
		print(l1)
	else:
		print(l1 + l2)


n = int(input())
a = []
for i in range(n):
	c = [int(x) for x in input().split(' ', 3)]
	a.append(c)
for i in range(n):
	if a[i][1] >= a[i][2] and a[i][3] >= a[i][0]:
		print(max(a[i][0], a[i][2]))
	else:
		print(a[i][0] + a[i][2])


t = int(input())
for i in range(t):
	(a, b, c, d) = map(int, input().split())
	if max(a, c) <= min(b, d):
		print(max(a, c))
	else:
		print(a + c)


import math as m
i = input()
inp = []
for a in range(0, int(i)):
	inp += [input()]
for s in inp:
	arr = s.split()
	(a, b, c, d) = (int(arr[0]), int(arr[1]), int(arr[2]), int(arr[3]))
	x = c <= a and a <= d
	y = a <= c and c <= b
	if x and (not y):
		print(str(a))
	elif y and (not x):
		print(str(c))
	elif y and x:
		print(str(min(a, c)))
	else:
		print(str(a + c))


answers = []
for _ in range(int(input())):
	(l1, r1, l2, r2) = map(int, input().split())
	a = set(range(l1, r1 + 1))
	b = set(range(l2, r2 + 1))
	temp = a.intersection(b)
	if temp:
		answers.append(f'{min(temp)}')
	else:
		answers.append(f'{l1 + l2}')
print('\n'.join(answers))


answers = []
for _ in range(int(input())):
	(l1, r1, l2, r2) = map(int, input().split())
	if max(l1, l2) <= min(r1, r2):
		answers.append(f'{max(l1, l2)}')
	else:
		answers.append(f'{l1 + l2}')
print('\n'.join(answers))


for _ in range(int(input())):
	(a, b, c, d) = map(int, input().split())
	if c > b or a > d:
		print(c + a)
	else:
		print(max(a, c))


def solve():
	(a, b, c, d) = map(int, input().split())
	if a <= c and b >= c:
		print(c)
	elif a >= c and a <= d:
		print(a)
	else:
		print(a + c)
for _ in range(int(input())):
	solve()


t = int(input())
for test in range(t):
	(l1, r1, l2, r2) = map(int, input().split())
	if l2 > l1:
		if r1 >= l2:
			print(l2)
		else:
			print(l1 + l2)
	elif r2 >= l1:
		print(l1)
	else:
		print(l1 + l2)


t = int(input())
for q in range(t):
	(l1, r1, l2, r2) = map(int, input().split())
	ans = 0
	if l2 >= l1 and l2 <= r1:
		ans = l2
	elif l1 >= l2 and l1 <= r2:
		ans = l1
	else:
		ans = l1 + l2
	print(ans)


t = int(input())
for _ in range(t):
	(l1, r1, l2, r2) = map(int, input().split())
	m1 = max(l1, l2)
	m2 = min(r1, r2)
	if m1 <= m2:
		print(m1)
	else:
		print(l1 + l2)