/*
#include <stdio.h>
// 1507. 4개의 직사각형 넓이
int main() {
int plane[100][100] = {0};
int x1, y1, x2, y2;
int area = 0;
for (int i = 0; i < 4; i++) {
scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
for (int y = y1; y < y2; y++) {
for (int x = x1; x < x2; x++) {
if (plane[y][x] == 0) {
plane[y][x] = 1;
area += 1;
}
}
}
}
printf("%d", area);
return 0;
}
*/
/*
#include <stdio.h>
// 1567. 함수로 배열의 부분합 리턴하기
int n, a, b, d[1010];
// 제출한 코드
long long subsetsum(int a, int b) {
long long sum = 0;
for (int i = a; i <= b; i++) {
sum += d[i];
}
return sum;
}
// 테스트용 코드
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &d[i]);
}
scanf("%d %d", &a, &b);
printf("%lld\n", subsetsum(a, b));
}
*/
/*
#include <stdio.h>
// 1535. 함수로 가장 큰 값 위치 리턴하기
int n, d[110];
// 제출한 코드
int f() {
int maxPos = 1;
int max = d[0];
for (int i = 1; i < n; i++) {
if (d[i] > max) {
maxPos = i + 1;
max = d[i];
}
}
return maxPos;
}
// 테스트용 코드
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &d[i]);
}
printf("%d", f());
return 0;
}
*/
/*
#include <stdio.h>
// 1558. 함수로 정수 뒤집어 리턴하기
long long n;
// 제출한 코드
long long f(long long n) {
long long result = 0;
long long powerOfTen = 1;
for (int i = 0; i < 19; i++) {
result *= 10;
result += n / powerOfTen % 10;
powerOfTen *= 10;
if (powerOfTen > n) {
break;
}
}
return result;
}
// 테스트용 코드
int main() {
scanf("%lld", &n);
printf("%lld\n", f(n));
}
*/
/*
#include <stdio.h>
// 1565. 함수로 최소공배수 리턴하기
int gcd(int p, int q) {
if(p == 0) {
return q;
}
return gcd(q % p, p);
}
// 제출한 코드
long long lcm(int p, int q) {
return (long long)p * q / gcd(p, q);
}
// 테스트용 코드
int main() {
int a, b;
scanf("%d %d", &a, &b);
printf("%lld\n", lcm(a, b));
}
*/
/*
#include <stdio.h>
// 1570. 함수로 Lower Bound 위치 리턴하기
int n, k, d[1010];
// 제출한 코드
int lower_bound(int k) {
if (k <= d[1]) {
return 1;
} else if (k > d[n]) {
return n + 1;
}
int pos = (n + 1) / 2 + 1;
int start = 2;
int end = n;
while (1) {
if (k > d[pos]) {
start = pos + 1;
} else if (k <= d[pos - 1]) {
end = pos - 1;
} else {
return pos;
}
pos = start + (end - start + 1) / 2;
}
}
// 테스트용 코드
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &d[i]);
scanf("%d", &k);
printf("%d\n", lower_bound(k));
}
*/
/*
#include <stdio.h>
// 1620. 자릿수의 합
int digitSum(int n) {
if (n < 10) {
return n;
}
int sum;
while (n >= 10) {
sum = 0;
while (n > 0) {
sum += n % 10;
n /= 10;
}
n = sum;
}
return sum;
}
int main() {
int n;
scanf("%d", &n);
printf("%d", digitSum(n));
return 0;
}
*/
/*
#include <stdio.h>
// 1901. 1부터 n까지 출력하기
int number = 1;
void printNumbers(int end) {
printf("%d\n", number);
number += 1;
if (number <= end) {
printNumbers(end);
}
}
int main() {
int n;
scanf("%d", &n);
printNumbers(n);
return 0;
}
*/
/*
#include <stdio.h>
// 1902. 1부터 n까지 역순으로 출력하기
void printNumbers(int n) {
printf("%d\n", n);
if (n > 1) {
printNumbers(n - 1);
}
}
int main() {
int n;
scanf("%d", &n);
printNumbers(n);
return 0;
}
*/
/*
#include <stdio.h>
// 1904. 두 수 사이의 홀수 출력하기
void printOddNumbers(int min, int max) {
if (min % 2 == 0) {
min += 1;
}
if (min <= max) {
printf("%d ", min);
printOddNumbers(min + 2, max);
}
}
int main() {
int a, b;
scanf("%d %d", &a, &b);
printOddNumbers(a, b);
return 0;
}
*/
/*
#include <stdio.h>
// 1905. 1부터 n까지 합 구하기
int numberSum(int n) {
if (n == 1) {
return 1;
} else {
return n + numberSum(n - 1);
}
}
int main() {
int n;
scanf("%d", &n);
printf("%d", numberSum(n));
return 0;
}
*/
/*
#include <stdio.h>
// 1912. 팩토리얼 계산
int factorial(int n) {
if (n == 1) {
return 1;
} else {
return n * factorial(n - 1);
}
}
int main() {
int n;
scanf("%d", &n);
printf("%d", factorial(n));
return 0;
}
*/