시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 (하단 참고)512 MB139383450.746%

문제

Albert는 정수 배열을 이용하여 특별한 정수쌍 세는 놀이를 즐겨한다. 우선 임의로 길이가 $N$인 두 정수 배열 $A$, $B$를 고른 후 아래와 같이 2차원 배열 $X$, $Y$, $Z$ 를 정의한다: $1 \le i \lt j \le N$ 인 정수 $i, j$에 대하여: $X(i, j) = A_i - A_j$ 이고 $Y(i, j) = B_i - B_j$ 이며 $Z(i, j) = | X(i, j) - Y(i, j) |$ 이다 ($Z(i, j)$는 절댓값이다). 마지막으로 $Z$를 이용하여 $C$를 정의한다: $C(D) = | \{(i, j) : Z(i, j) \le D \} |$. 즉, $C(D)$는 $Z(i, j)$ 가 $D$ 이하인 "특별한 정수쌍" $(i, j)$의 개수를 나타낸다 (물론 $1 \le i \lt j \le N$ 인 경우만 고려한다).

예를 들어 $N = 5$, $A = [2, 4, 6, 4, 2]$, $B = [9, 1, 3, 7, 5]$ 라 하자. 아래 그림은 순서대로 $X$, $Y$, $Z$ 2차원 배열의 값을 나타낸다. 행은 i인덱스, 열은 j인덱스를 나타낸다.

위 정보를 활용하면 다양한 $D$ 값에 대하여 $C(D)$ 값을 계산할 수 있다:

  • $D$ = 0: $Z(2, 3) = Z(4, 5) = 0$ 이므로 $C(0) = 2$ 가 된다.
  • $D$ = 4: $Z(i, j) = 0$ 인 경우가 두 쌍, $Z(i, j) = 4$인 경우가 두 쌍 있으므로 $C(4) = 4$가 된다.
  • $D$ = 6: 이 경우 $Z(i, j) = 6$ 인 $(i, j)$ 쌍이 4개이므로, 앞서 언급한 네 쌍을 포함하여 $C(6) = 8$ 이 된다.
  • $D$ = 10: 이 경우 모든 쌍을 포함하므로 $C(10) = 10$ 이 된다.
  • $D$ = 20: 이 경우도 위와 마찬가지로 $C(20) = 10$이다.

$A$, $B$, $D$가 주어졌을 때 $C(D)$값을 계산하는 문제는 너무 쉽기 때문에 Albert는 다음과 같은 새로운 놀이를 생각했다: $A$, $B$와 함께 임의의 정수 $K$가 주어졌을 때 $C(D) = K$ 가 되는 $D$가 존재하는지 판별하고, 존재한다면 그 중 가장 작은 $D$값을 찾아보자.

입력

첫 줄에 테스트 케이스의 수 $T$가 주어진다.

각 테스트 케이스의 첫 줄에는 $N$과 $K$가 주어진다. 둘째 줄에는 배열 $A$의 정수 $N$개가 공백으로 구분되어 주어진다. 셋째 줄에는 배열 $B$의 정수 $N$개가 공백으로 구분되어 주어진다.

출력

각 테스트 케이스의 정답을 각 줄에 출력한다. 만약 조건을 만족하는 $D$가 없다면 -1을 출력한다.

제한

  • $1 \le T \le 5$
  • $2 \le N \le 50000$
  • $0 \le K \le N \times (N-1) / 2$
  • $1 \le i \le N$ 인 $i$ 에 대하여: $0 \le A[i], B[i] \le 10^5$

예제 입력 1

5
5 2
2 4 6 4 2
9 1 3 7 5
5 4
2 4 6 4 2
9 1 3 7 5
5 6
2 4 6 4 2
9 1 3 7 5
5 8
2 4 6 4 2
9 1 3 7 5
5 10
2 4 6 4 2
9 1 3 7 5

예제 출력 1

0
4
-1
6
10

예제 1-5: 본문에서 다룬 예제이며 $K$ 값만 바뀌는 경우를 보여준다.

예제 입력 2

1
9 18
1 2 3 4 5 4 3 2 1
5 4 3 2 1 2 3 4 5

예제 출력 2

2

예제 1: 총 18개의 $(i, j)$쌍을 제외하고는 모두 $Z(i, j) \gt 2$ 인데, $Z(1, 9)$ = $Z(2, 8)$ = $Z(3, 7)$ = $Z(4, 6)$ = $0$ 이고 $Z(1, 2)$ = $Z(1, 8)$ = $Z(2, 3)$ = $Z(2, 7)$ = $Z(2, 9)$ = $Z(3, 4)$ = $Z(3, 6)$ = $Z(3, 8)$ = $Z(4, 5)$ = $Z(4, 7)$ = $Z(5, 6)$ = $Z(6, 7)$ = $Z(7, 8)$ = $Z(8, 9)$ = $2$ 이므로 $C(2) = 18$ 이다.

W3sicHJvYmxlbV9pZCI6IjI3MzYyIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVkMmI5XHViY2M0XHVkNTVjIFx1YzgxNVx1YzIxOFx1YzMwZCBcdWMxMzhcdWFlMzAiLCJkZXNjcmlwdGlvbiI6IjxwPkFsYmVydFx1YjI5NCBcdWM4MTVcdWMyMTggXHViYzMwXHVjNWY0XHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU1OFx1YzVlYyBcdWQyYjlcdWJjYzRcdWQ1NWMgXHVjODE1XHVjMjE4XHVjMzBkIFx1YzEzOFx1YjI5NCBcdWIxODBcdWM3NzRcdWI5N2MgXHVjOTkwXHVhY2E4XHVkNTVjXHViMmU0LiBcdWM2YjBcdWMxMjAgXHVjNzg0XHVjNzU4XHViODVjIFx1YWUzOFx1Yzc3NFx1YWMwMCAkTiRcdWM3NzggXHViNDUwIFx1YzgxNVx1YzIxOCBcdWJjMzBcdWM1ZjQgJEEkLCAkQiRcdWI5N2MgXHVhY2UwXHViOTc4IFx1ZDZjNCBcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHVjNzc0IDJcdWNjMjhcdWM2ZDAgXHViYzMwXHVjNWY0ICRYJCwgJFkkLCAkWiQgXHViOTdjIFx1YzgxNVx1Yzc1OFx1ZDU1Y1x1YjJlNDogJDEgXFxsZSBpIFxcbHQgaiBcXGxlIE4kIFx1Yzc3OCBcdWM4MTVcdWMyMTggJGksIGokXHVjNWQwIFx1YjMwMFx1ZDU1OFx1YzVlYzogJFgoaSwgaikgPSBBX2kgLSBBX2okIFx1Yzc3NFx1YWNlMCAkWShpLCBqKSA9IEJfaSAgLSBCX2okIFx1Yzc3NFx1YmE3MCAkWihpLCBqKSA9IHwgWChpLCBqKSAtIFkoaSwgaikgfCQgXHVjNzc0XHViMmU0ICgkWihpLCBqKSRcdWIyOTQgXHVjODA4XHViMzEzXHVhYzEyXHVjNzc0XHViMmU0KS4gXHViOWM4XHVjOWMwXHViOWM5XHVjNzNjXHViODVjICRaJFx1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1NThcdWM1ZWMgJEMkXHViOTdjIFx1YzgxNVx1Yzc1OFx1ZDU1Y1x1YjJlNDogJEMoRCkgPSB8IFxceyhpLCBqKSA6IFooaSwgaikgXFxsZSBEIFxcfSB8JC4gXHVjOTg5LCAkQyhEKSRcdWIyOTQgJFooaSwgaikkIFx1YWMwMCAkRCQgXHVjNzc0XHVkNTU4XHVjNzc4ICZxdW90O1x1ZDJiOVx1YmNjNFx1ZDU1YyBcdWM4MTVcdWMyMThcdWMzMGQmcXVvdDsgJChpLCBqKSRcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNCAoXHViYjNjXHViODYwICQxIFxcbGUgaSBcXGx0IGogXFxsZSBOJCBcdWM3NzggXHVhY2JkXHVjNmIwXHViOWNjIFx1YWNlMFx1YjgyNFx1ZDU1Y1x1YjJlNCkuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQgJE4gPSA1JCwgJEEgPSBbMiwgNCwgNiwgNCwgMl0kLCAkQiA9IFs5LCAxLCAzLCA3LCA1XSQgXHViNzdjIFx1ZDU1OFx1Yzc5MC4gXHVjNTQ0XHViNzk4IFx1YWRmOFx1YjliY1x1Yzc0MCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgJFgkLCAkWSQsICRaJCAyXHVjYzI4XHVjNmQwIFx1YmMzMFx1YzVmNFx1Yzc1OCBcdWFjMTJcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LiBcdWQ1ODlcdWM3NDAgaVx1Yzc3OFx1YjM3MVx1YzJhNCwgXHVjNWY0XHVjNzQwIGpcdWM3NzhcdWIzNzFcdWMyYTRcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcL2E3Mjc4MzE4LTViYWUtNGI0MS04MDRiLTQ5Yzc4MjA3YjE1ZFwvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJoZWlnaHQ6IDE2MnB4OyB3aWR0aDogNjAwcHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YzcwNCBcdWM4MTVcdWJjZjRcdWI5N2MgXHVkNjVjXHVjNmE5XHVkNTU4XHViYTc0IFx1YjJlNFx1YzU5MVx1ZDU1YyAkRCQgXHVhYzEyXHVjNWQwIFx1YjMwMFx1ZDU1OFx1YzVlYyAkQyhEKSQgXHVhYzEyXHVjNzQ0IFx1YWNjNFx1YzBiMFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0OjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPiREJCA9IDA6ICRaKDIsIDMpID0gWig0LCA1KSA9IDAkIFx1Yzc3NFx1YmJjMFx1Yjg1YyAkQygwKSA9IDIkIFx1YWMwMCBcdWI0MWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPiREJCA9IDQ6ICRaKGksIGopID0gMCQgXHVjNzc4IFx1YWNiZFx1YzZiMFx1YWMwMCBcdWI0NTAgXHVjMzBkLCAkWihpLCBqKSA9IDQkXHVjNzc4IFx1YWNiZFx1YzZiMFx1YWMwMCBcdWI0NTAgXHVjMzBkIFx1Yzc4OFx1YzczY1x1YmJjMFx1Yjg1YyAkQyg0KSA9IDQkXHVhYzAwIFx1YjQxY1x1YjJlNC48XC9saT5cclxuXHQ8bGk+JEQkID0gNjogXHVjNzc0IFx1YWNiZFx1YzZiMCAkWihpLCBqKSA9IDYkIFx1Yzc3OCAkKGksIGopJCBcdWMzMGRcdWM3NzQgNFx1YWMxY1x1Yzc3NFx1YmJjMFx1Yjg1YywgXHVjNTVlXHVjMTFjIFx1YzViOFx1YWUwOVx1ZDU1YyBcdWIxMjQgXHVjMzBkXHVjNzQ0IFx1ZDNlY1x1ZDU2OFx1ZDU1OFx1YzVlYyAkQyg2KSA9IDgkIFx1Yzc3NCBcdWI0MWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPiREJCA9IDEwOiBcdWM3NzQgXHVhY2JkXHVjNmIwIFx1YmFhOFx1YjRlMCBcdWMzMGRcdWM3NDQgXHVkM2VjXHVkNTY4XHVkNTU4XHViYmMwXHViODVjICRDKDEwKSA9IDEwJCBcdWM3NzQgXHViNDFjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT4kRCQgPSAyMDogXHVjNzc0IFx1YWNiZFx1YzZiMFx1YjNjNCBcdWM3MDRcdWM2NDAgXHViOWM4XHVjYzJjXHVhYzAwXHVjOWMwXHViODVjICRDKDIwKSA9IDEwJFx1Yzc3NFx1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD4kQSQsICRCJCwgJEQkXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMgJEMoRCkkXHVhYzEyXHVjNzQ0IFx1YWNjNFx1YzBiMFx1ZDU1OFx1YjI5NCBcdWJiMzhcdWM4MWNcdWIyOTQgXHViMTA4XHViYjM0IFx1YzI3ZFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgQWxiZXJ0XHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVjMGM4XHViODVjXHVjNmI0IFx1YjE4MFx1Yzc3NFx1Yjk3YyBcdWMwZGRcdWFjMDFcdWQ1ODhcdWIyZTQ6ICRBJCwgJEIkXHVjNjQwIFx1ZDU2OFx1YWVkOCBcdWM3ODRcdWM3NThcdWM3NTggXHVjODE1XHVjMjE4ICRLJFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjICRDKEQpID0gSyQgXHVhYzAwIFx1YjQxOFx1YjI5NCAkRCRcdWFjMDAgXHVjODc0XHVjN2FjXHVkNTU4XHViMjk0XHVjOWMwIFx1ZDMxMFx1YmNjNFx1ZDU1OFx1YWNlMCwgXHVjODc0XHVjN2FjXHVkNTVjXHViMmU0XHViYTc0IFx1YWRmOCBcdWM5MTEgXHVhYzAwXHVjN2E1IFx1Yzc5MVx1Yzc0MCAkRCRcdWFjMTJcdWM3NDQgXHVjYzNlXHVjNTQ0XHViY2Y0XHVjNzkwLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YzIxOCAkVCRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWIgXHVjOTA0XHVjNWQwXHViMjk0ICROJFx1YWNmYyAkSyRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YmMzMFx1YzVmNCAkQSRcdWM3NTggXHVjODE1XHVjMjE4ICROJFx1YWMxY1x1YWMwMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjMTRiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWJjMzBcdWM1ZjQgJEIkXHVjNzU4IFx1YzgxNVx1YzIxOCAkTiRcdWFjMWNcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjODE1XHViMmY1XHVjNzQ0IFx1YWMwMSBcdWM5MDRcdWM1ZDAgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QgXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCAkRCRcdWFjMDAgXHVjNWM2XHViMmU0XHViYTc0IC0xXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4iLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+JDEgXFxsZSBUIFxcbGUgNSQ8XC9saT5cclxuXHQ8bGk+JDIgXFxsZSBOIFxcbGUgNTAwMDAkPFwvbGk+XHJcblx0PGxpPiQwIFxcbGUgSyBcXGxlIE4gXFx0aW1lcyAoTi0xKSBcLyAyJDxcL2xpPlxyXG5cdDxsaT4kMSBcXGxlIGkgXFxsZSBOJCBcdWM3NzggJGkkIFx1YzVkMCBcdWIzMDBcdWQ1NThcdWM1ZWM6ICQwIFxcbGUgQVtpXSwgQltpXSBcXGxlIDEwXjUkPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJzYW1wbGVfZXhwbGFpbl8xIjoiPHA+XHVjNjA4XHVjODFjIDEtNTogXHViY2Y4XHViYjM4XHVjNWQwXHVjMTFjIFx1YjJlNFx1YjhlYyBcdWM2MDhcdWM4MWNcdWM3NzRcdWJhNzAgJEskIFx1YWMxMlx1YjljYyBcdWJjMTRcdWIwMGNcdWIyOTQgXHVhY2JkXHVjNmIwXHViOTdjIFx1YmNmNFx1YzVlY1x1YzkwMFx1YjJlNC48XC9wPlxyXG4iLCJzYW1wbGVfZXhwbGFpbl8yIjoiPHA+XHVjNjA4XHVjODFjIDE6Jm5ic3A7XHVjZDFkIDE4XHVhYzFjXHVjNzU4ICQoaSwgaikkXHVjMzBkXHVjNzQ0IFx1YzgxY1x1YzY3OFx1ZDU1OFx1YWNlMFx1YjI5NCBcdWJhYThcdWI0NTAgJFooaSwgaikgXFxndCAyJCBcdWM3NzhcdWIzNzAsJm5ic3A7JFooMSwgOSkkID0gJFooMiwgOCkkID0gJFooMywgNykkID0gJFooNCwgNikkID0gJDAkIFx1Yzc3NFx1YWNlMCAkWigxLCAyKSQgPSAkWigxLCA4KSQgPSAkWigyLCAzKSQgPSAkWigyLCA3KSQgPSAkWigyLCA5KSQgPSAkWigzLCA0KSQgPSAkWigzLCA2KSQgPSAkWigzLCA4KSQgPSAkWig0LCA1KSQgPSAkWig0LCA3KSQgPSAkWig1LCA2KSQgPSAkWig2LCA3KSQgPSAkWig3LCA4KSQgPSAkWig4LCA5KSQgPSAkMiQgXHVjNzc0XHViYmMwXHViODVjICRDKDIpID0gMTgkIFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4ifSx7InByb2JsZW1faWQiOiIyNzM2MiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkNvdW50aW5nIFNwZWNpYWwgSW50ZWdlciBQYWlycyIsImRlc2NyaXB0aW9uIjoiPHA+QWxiZXJ0IGxvdmVzIHRvIGNvdW50IHRoZSBudW1iZXIgb2YgU3BlY2lhbCBJbnRlZ2VyIFBhaXJzIHVzaW5nIHR3byBpbnRlZ2VyIGFycmF5cy4gRmlyc3QsIEFsYmVydCBjaG9vc2VzIHR3byBpbnRlZ2VyIGFycmF5cyAkQSQgYW5kICRCJCBvZiBsZW5ndGggJE4kLCBhbmQgZGVmaW5lIHR3by1kaW1lbnNpb25hbCBhcnJheXMgJFgkLCAkWSQsIGFuZCAkWiQgYXMgZm9sbG93czogRm9yICRpLCBqJCB3aXRoICQxIFxcbGUgaSBcXGx0IGogXFxsZSBOJDombmJzcDskWChpLCBqKSZuYnNwOz0gQV9pIC0gQV9qJCwgJFkoaSwgaikmbmJzcDs9IEJfaSZuYnNwOyAtIEJfaiQsIGFuZCAkWihpLCBqKSA9IHwgWChpLCBqKSAtIFkoaSwgaikgfCQgKGkuZS4gJFooaSwgaikkIGlzIHRoZSZuYnNwO2Fic29sdXRlIHZhbHVlKS4gTGFzdGx5LCBoZSB1c2VzICRaJCB0byBkZWZpbmUgYSZuYnNwO2Z1bmN0aW9uJm5ic3A7JEMkOiAkQyhEKSA9IHwgXFx7KGksIGopIDogWihpLCBqKSBcXGxlIEQgXFx9IHwkLiBJbiBvdGhlciB3b3JkcywmbmJzcDskQyhEKSQgaXMgdGhlIG51bWJlciBvZiAmcXVvdDtTcGVjaWFsIEludGVnZXIgUGFpcnMmcXVvdDsgJChpLCBqKSQgc3VjaCB0aGF0Jm5ic3A7JFooaSwgaikkIGlzIG5vIGdyZWF0ZXIgdGhhbiZuYnNwOyREJCAob2YgY291cnNlLCBvbmx5IGZvciAkMSBcXGxlIGkgXFxsdCBqIFxcbGUgTiQpLjxcL3A+XHJcblxyXG48cD5Gb3IgaW5zdGFuY2UsIHN1cHBvc2UmbmJzcDsgJE4gPSA1JCwgJEEgPSBbMiwgNCwgNiwgNCwgMl0kLCBhbmQgJEIgPSBbOSwgMSwgMywgNywgNV0kLiBUaGUgdGFibGVzIHNob3duIGJlbG93IHNob3cgdGhlIHZhbHVlcyBvZiZuYnNwOyRYJCwgJFkkLCBhbmQgJFokLiBSb3dzIGFyZSBpbmRleGVkIGJ5ICRpJCBhbmQgY29sdW1ucyBieSAkaiQuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvYTcyNzgzMTgtNWJhZS00YjQxLTgwNGItNDljNzgyMDdiMTVkXC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cImhlaWdodDogMTYycHg7IHdpZHRoOiA2MDBweDtcIiBcLz48YnIgXC8+XHJcblVzaW5nIHRoZSBpbmZvcm1hdGlvbiBhYm92ZSwgd2UgY2FuIGNhbGN1bGF0ZSAkQyhEKSQgZm9yIGRpZmZlcmVudCB2YWx1ZXMgb2YgJEQkOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPiREJCA9IDA6IEFzICRaKDIsIDMpID0gWig0LCA1KSA9IDAkLCB3ZSBoYXZlJm5ic3A7JEMoMCkgPSAyJC48XC9saT5cclxuXHQ8bGk+JEQkID0gNDogVGhlcmUgYXJlIHR3byAkKGksIGopJCBwYWlycyB3aXRoICRaKGksIGopID0gMCQgYW5kIHR3byB3aXRoICRaKGksIGopID0gNCQmbmJzcDtzbyB0aGF0ICRDKDQpID0gNCQuPFwvbGk+XHJcblx0PGxpPiREJCA9IDY6IEluIHRoaXMgY2FzZSwgdGhlcmUgYXJlIDQgJChpLCBqKSQgcGFpcnMgd2l0aCAkWihpLCBqKSA9IDYkIHNvIHRoYXQgJEMoNikgPSA4JCBpbmNsdWRpbmcgdGhlIGZvdXIgcGFpcnMgZnJvbSBlYXJsaWVyLjxcL2xpPlxyXG5cdDxsaT4kRCQgPSAxMDogSW4gdGhpcyBjYXNlLCBhbGwgcGFpcnMgc2hvdWxkIGJlIGNvdW50ZWQgc28gdGhhdCZuYnNwOyRDKDEwKSA9IDEwJC48XC9saT5cclxuXHQ8bGk+JEQkID0gMjA6IFNpbWlsYXIgdG8gdGhlIGFib3ZlLCB3ZSBoYXZlICRDKDIwKSA9IDEwJC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5TaW5jZSBpdCBpcyB0b28gZWFzeSB0byBjb21wdXRlICRDKEQpJCB3aGVuJm5ic3A7JEEkLCAkQiQsIGFuZCAkRCQgYXJlIGdpdmVuLCBBbGJlcnQgY2FtZSB1cCB3aXRoIGEgZGlmZmVyZW50IHByb2JsZW06IEdpdmVuICRBJCwgJEIkIGFuZCBhbiBhcmJpdHJhcnkgaW50ZWdlciAkSyQsIGRldGVybWluZSBpZiBhbiBpbnRlZ2VyICREJCBleGlzdHMgd2l0aCZuYnNwOyRDKEQpID0gSyQsIGFuZCBpZiBzbywgZmluZCB0aGUgc21hbGxlc3Qgc3VjaCAkRCQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQgd2lsbCBjb250YWluICRUJCwgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzLjxcL3A+XHJcblxyXG48cD5UaGUgZmlyc3QgbGluZSBvZiBlYWNoIHRlc3QgY2FzZSB3aWxsIGNvbnRhaW4gJE4kIGFuZCAkSyQsIHNlcGFyYXRlZCBieSB3aGl0ZXNwYWNlLiBUaGUgc2Vjb25kIGxpbmUgd2lsbCBjb250YWluICROJCBpbnRlZ2VycyBvZiB0aGUgYXJyYXkgJEEkLCBzZXBhcmF0ZWQgYnkgd2hpdGVzcGFjZS4gVGhlIHRoaXJkIGxpbmUgd2lsbCBjb250YWluICROJCBpbnRlZ2VycyBvZiB0aGUgYXJyYXkgJEIkLCBzZXBhcmF0ZWQgYnkgd2hpdGVzcGFjZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIGFuc3dlciBvZiBlYWNoIHRlc3QgY2FzZSBpbiBlYWNoIGxpbmUuIElmIHRoZXJlIGV4aXN0cyBubyAkRCQgdGhhdCBzYXRpc2ZpZXMgdGhlIHJlcXVpcmVtZW50cywgb3V0cHV0IC0xLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2giLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+JDEgXFxsZSZuYnNwO1QmbmJzcDtcXGxlIDUkPFwvbGk+XHJcblx0PGxpPiQyIFxcbGUmbmJzcDtOJm5ic3A7XFxsZSZuYnNwOzUwMDAwJDxcL2xpPlxyXG5cdDxsaT4kMCBcXGxlJm5ic3A7SyZuYnNwO1xcbGUgTiBcXHRpbWVzJm5ic3A7KE4tMSkgXC8gMiQ8XC9saT5cclxuXHQ8bGk+Rm9yIGVhY2ggJGkkIHdpdGgmbmJzcDskMSBcXGxlIGkgXFxsZSBOJDogJDAgXFxsZSBBW2ldLCBCW2ldIFxcbGUgMTBeNSQ8XC9saT5cclxuPFwvdWw+XHJcbiIsInNhbXBsZV9leHBsYWluXzEiOiI8cD5DYXNlcyAxLTU6IFRoZSBzYW1lIGV4YW1wbGUgZnJvbSB0aGUgcHJvYmxlbSBzdGF0ZW1lbnQgaXMgYmVpbmcgdXNlZCwgYnV0IHdpdGggZGlmZmVyZW50IHZhbHVlcyBvZiAkSyQuPFwvcD5cclxuIiwic2FtcGxlX2V4cGxhaW5fMiI6IjxwPkNhc2UgMTombmJzcDtBbGwgYnV0IDE4IHBhaXJzIGhhdmUgJFooaSwgaikgXFxndCAyJCB3aGVyZSBhcyZuYnNwOyRaKDEsIDkpJCA9ICRaKDIsIDgpJCA9ICRaKDMsIDcpJCA9ICRaKDQsIDYpJCA9ICQwJCBhbmQgJFooMSwgMikkID0gJFooMSwgOCkkID0gJFooMiwgMykkID0gJFooMiwgNykkID0gJFooMiwgOSkkID0gJFooMywgNCkkID0gJFooMywgNikkID0gJFooMywgOCkkID0gJFooNCwgNSkkID0gJFooNCwgNykkID0gJFooNSwgNikkID0gJFooNiwgNykkID0gJFooNywgOCkkID0gJFooOCwgOSkkID0gJDIkLiBIZW5jZSwgJEMoMikgPSAxOCQuPFwvcD5cclxuIn1d

시간 제한

  • Java 8: 2 초
  • Python 3: 3 초
  • PyPy3: 3 초
  • Java 8 (OpenJDK): 2 초
  • Java 11: 2 초
  • Java 15: 2 초