시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 512 MB242926037.500%

문제

평면에 N개의 점 P1(x1, y1), P2(x2, y2), . . . , PN(xN, yN)이 주어지며, 각각의 점들은 총 K개의 색깔 중 하나를 가지고 있다. 각 점의 색깔은 {1, 2, . . . , K} 중의 한 정수로 표현된다.

어떤 정사각형이 각 K개의 색깔에 대해 해당 색깔의 점을 하나 이상 포함하고 있다면, 이 정사각형을 화려한 정사각형이라고 부른다. 변의 길이를 최소로 하는 화려한 정사각형을 찾아서 그 변의 길이를 출력하는 프로그램을 작성하라.

단, 여기서 정사각형은 네 변이 모두 수평 혹은 수직인 것에 한정하며, 정사각형의 내부가 아닌 경계에 놓인 점들도 그 정사각형에 포함된다고 생각한다. 정사각형의 한 변의 길이가 0이 되어 점으로 나타나는 경우도 정사각형의 한 경우로 간주한다.

입력

첫 번째 줄에 두 정수 N과 K가 공백 하나를 사이로 두고 주어진다.

이후 N 개의 줄이 주어진다. 이 중 i 번째 줄에는 세 개의 정수 xi, yi, ki가 공백 하나 씩을 사이에 두고 주어지며, 입력으로 주어지는 각 점의 좌표 (xi, yi)와 그 점의 색깔 ki을 의미한다.

출력

첫 번째 줄에 문제의 정답을 출력한다.

제한

  • 2 ≤ N ≤ 100 000
  • 2 ≤ K ≤ N
  • 모든 i (1 ≤ i ≤ N)에 대해, xi와 yi는 1 이상 250 000 이하의 정수이다.
  • 모든 색 1 ≤ k ≤ K에 대해, N개의 점들 중 색깔이 k인 점이 최소 하나 존재한다.

서브태스크

번호 배점 제한
1 3

N ≤ 50, 모든 i (1 ≤ i ≤ N)에 대해 xi, yi ≤ 50

2 10

K ≤ 50, 모든 i (1 ≤ i ≤ N)에 대해 xi, yi ≤ 2 500

3 12

K = 2

4 5

N ≤ 50

5 8

N ≤ 150

6 9

N ≤ 600

7 13

N ≤ 2 500

8 40

추가 제약 조건 없음

예제 입력 1

5 2
4 2 1
5 3 1
5 4 2
4 5 2
3 8 2

예제 출력 1

1

예제 입력 2

5 3
4 2 1
5 3 1
5 4 2
4 5 2
3 8 3

예제 출력 2

5

예제 입력 3

4 2
1 1 1
1 1 1
1 1 2
1 1 2

예제 출력 3

0
W3sicHJvYmxlbV9pZCI6IjIwMTkzIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVkNjU0XHViODI0XHVkNTVjIFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNSIsImRlc2NyaXB0aW9uIjoiPHA+XHVkM2M5XHViYTc0XHVjNWQwIE5cdWFjMWNcdWM3NTggXHVjODEwIFA8c3ViPjE8XC9zdWI+KHg8c3ViPjE8XC9zdWI+LCB5PHN1Yj4xPFwvc3ViPiksIFA8c3ViPjI8XC9zdWI+KHg8c3ViPjI8XC9zdWI+LCB5PHN1Yj4yPFwvc3ViPiksIC4gLiAuICwgUDxzdWI+TjxcL3N1Yj4oeDxzdWI+TjxcL3N1Yj4sIHk8c3ViPk48XC9zdWI+KVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWM4MTBcdWI0ZTRcdWM3NDAgXHVjZDFkIEtcdWFjMWNcdWM3NTggXHVjMGM5XHVhZTU0IFx1YzkxMSBcdWQ1NThcdWIwOThcdWI5N2MgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1YzgxMFx1Yzc1OCBcdWMwYzlcdWFlNTRcdWM3NDAgezEsIDIsIC4gLiAuICwgS30gXHVjOTExXHVjNzU4IFx1ZDU1YyBcdWM4MTVcdWMyMThcdWI4NWMgXHVkNDVjXHVkNjA0XHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1YjRcdWI1YTQgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVjNzc0IFx1YWMwMSBLXHVhYzFjXHVjNzU4IFx1YzBjOVx1YWU1NFx1YzVkMCBcdWIzMDBcdWQ1NzQgXHVkNTc0XHViMmY5IFx1YzBjOVx1YWU1NFx1Yzc1OCBcdWM4MTBcdWM3NDQgXHVkNTU4XHViMDk4IFx1Yzc3NFx1YzBjMSBcdWQzZWNcdWQ1NjhcdWQ1NThcdWFjZTAgXHVjNzg4XHViMmU0XHViYTc0LCBcdWM3NzQgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVjNzQ0IDxzdHJvbmc+XHVkNjU0XHViODI0XHVkNTVjIFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNTxcL3N0cm9uZz5cdWM3NzRcdWI3N2NcdWFjZTAgXHViZDgwXHViOTc4XHViMmU0LiBcdWJjYzBcdWM3NTggXHVhZTM4XHVjNzc0XHViOTdjIFx1Y2Q1Y1x1YzE4Y1x1Yjg1YyBcdWQ1NThcdWIyOTQgXHVkNjU0XHViODI0XHVkNTVjIFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc0NCBcdWNjM2VcdWM1NDRcdWMxMWMgXHVhZGY4IFx1YmNjMFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWI3N2MuPFwvcD5cclxuXHJcbjxwPlx1YjJlOCwgXHVjNWVjXHVhZTMwXHVjMTFjIFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc0MCBcdWIxMjQgXHViY2MwXHVjNzc0IFx1YmFhOFx1YjQ1MCBcdWMyMThcdWQzYzkgXHVkNjM5XHVjNzQwIFx1YzIxOFx1YzljMVx1Yzc3OCBcdWFjODNcdWM1ZDAgXHVkNTVjXHVjODE1XHVkNTU4XHViYTcwLCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NTggXHViMGI0XHViZDgwXHVhYzAwIFx1YzU0NFx1YjJjYyBcdWFjYmRcdWFjYzRcdWM1ZDAgXHViMTkzXHVjNzc4IFx1YzgxMFx1YjRlNFx1YjNjNCBcdWFkZjggXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVjNWQwIFx1ZDNlY1x1ZDU2OFx1YjQxY1x1YjJlNFx1YWNlMCBcdWMwZGRcdWFjMDFcdWQ1NWNcdWIyZTQuIFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWQ1NWMgXHViY2MwXHVjNzU4IFx1YWUzOFx1Yzc3NFx1YWMwMCAwXHVjNzc0IFx1YjQxOFx1YzViNCBcdWM4MTBcdWM3M2NcdWI4NWMgXHViMDk4XHVkMGMwXHViMDk4XHViMjk0IFx1YWNiZFx1YzZiMFx1YjNjNCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NTggXHVkNTVjIFx1YWNiZFx1YzZiMFx1Yjg1YyBcdWFjMDRcdWM4ZmNcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWI0NTAgXHVjODE1XHVjMjE4IE5cdWFjZmMgS1x1YWMwMCBcdWFjZjVcdWJjMzEgXHVkNTU4XHViMDk4XHViOTdjIFx1YzBhY1x1Yzc3NFx1Yjg1YyBcdWI0NTBcdWFjZTAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWQ2YzQgTiBcdWFjMWNcdWM3NTggXHVjOTA0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0IFx1YzkxMSBpIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMTM4IFx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMTggeDxzdWI+aTxcL3N1Yj4sIHk8c3ViPmk8XC9zdWI+LCBrPHN1Yj5pPFwvc3ViPlx1YWMwMCBcdWFjZjVcdWJjMzEgXHVkNTU4XHViMDk4IFx1YzUyOVx1Yzc0NCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHViNDUwXHVhY2UwIFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCwgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWFjMDEgXHVjODEwXHVjNzU4IFx1Yzg4Y1x1ZDQ1YyAoeDxzdWI+aTxcL3N1Yj4sIHk8c3ViPmk8XC9zdWI+KVx1YzY0MCBcdWFkZjggXHVjODEwXHVjNzU4IFx1YzBjOVx1YWU1NCBrPHN1Yj5pPFwvc3ViPlx1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViYjM4XHVjODFjXHVjNzU4IFx1YzgxNVx1YjJmNVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIiwibGltaXQiOiI8dWw+XHJcblx0PGxpPjIgJmxlOyBOICZsZTsgMTAwIDAwMDxcL2xpPlxyXG5cdDxsaT4yICZsZTsgSyAmbGU7IE48XC9saT5cclxuXHQ8bGk+XHViYWE4XHViNGUwIGkgKDEgJmxlOyBpICZsZTsgTilcdWM1ZDAgXHViMzAwXHVkNTc0LCB4PHN1Yj5pPFwvc3ViPlx1YzY0MCB5PHN1Yj5pPFwvc3ViPlx1YjI5NCAxIFx1Yzc3NFx1YzBjMSAyNTAgMDAwIFx1Yzc3NFx1ZDU1OFx1Yzc1OCBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YmFhOFx1YjRlMCBcdWMwYzkgMSAmbGU7IGsgJmxlOyBLXHVjNWQwIFx1YjMwMFx1ZDU3NCwgTlx1YWMxY1x1Yzc1OCBcdWM4MTBcdWI0ZTQgXHVjOTExIFx1YzBjOVx1YWU1NFx1Yzc3NCBrXHVjNzc4IFx1YzgxMFx1Yzc3NCBcdWNkNWNcdWMxOGMgXHVkNTU4XHViMDk4IFx1Yzg3NFx1YzdhY1x1ZDU1Y1x1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcbiIsInN1YnRhc2sxIjoiPHA+TiAmbGU7IDUwLCBcdWJhYThcdWI0ZTAgaSAoMSAmbGU7IGkgJmxlOyBOKVx1YzVkMCBcdWIzMDBcdWQ1NzQgeDxzdWI+aTxcL3N1Yj4sIHk8c3ViPmk8XC9zdWI+ICZsZTsgNTA8XC9wPlxyXG4iLCJzdWJ0YXNrMiI6IjxwPksgJmxlOyA1MCwgXHViYWE4XHViNGUwIGkgKDEgJmxlOyBpICZsZTsgTilcdWM1ZDAgXHViMzAwXHVkNTc0IHg8c3ViPmk8XC9zdWI+LCB5PHN1Yj5pPFwvc3ViPiAmbGU7IDIgNTAwPFwvcD5cclxuIiwic3VidGFzazMiOiI8cD5LID0gMjxcL3A+XHJcbiIsInN1YnRhc2s0IjoiPHA+TiAmbGU7IDUwPFwvcD5cclxuIiwic3VidGFzazUiOiI8cD5OICZsZTsgMTUwPFwvcD5cclxuIiwic3VidGFzazYiOiI8cD5OICZsZTsgNjAwPFwvcD5cclxuIiwic3VidGFzazciOiI8cD5OICZsZTsgMiA1MDA8XC9wPlxyXG4iLCJzdWJ0YXNrOCI6IjxwPlx1Y2Q5NFx1YWMwMCBcdWM4MWNcdWM1N2QgXHVjODcwXHVhYzc0IFx1YzVjNlx1Yzc0YzxcL3A+XHJcbiJ9LHsicHJvYmxlbV9pZCI6IjIwMTkzIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQ29sb3JmdWwgU3F1YXJlcyIsImRlc2NyaXB0aW9uIjoiPHA+VGhlcmUgYXJlICROJCBwb2ludHMgb24gYSBwbGFuZTogJFBfMSQgJCh4XzEsIHlfMSkkLCAkUF8yJCAkKHhfMiwgeV8yKSQsIFxcbGRvdHMsICRQX04kICQoeF9OLCB5X04pJC4gRWFjaCBwb2ludCBoYXMgYSBjb2xvciBkZW5vdGVkIGJ5IGFuIGludGVnZXIgZnJvbSAkMSQgdG8gJEskLjxcL3A+XHJcblxyXG48cD5Db25zaWRlciBhIHNxdWFyZSB3aXRoIGVkZ2VzIHBhcmFsbGVsIHRvIGNvb3JkaW5hdGUgYXhlcy4gVGhlIHNxdWFyZSBpcyA8ZW0+Y29sb3JmdWw8XC9lbT4gaWYgaXQgY29udGFpbnMgcG9pbnRzIG9mIGFsbCAkSyQgY29sb3JzIGluc2lkZSBvciBvbiBpdHMgYm9yZGVyLiBJdCBpcyBhbGxvd2VkIGZvciB0aGUgc3F1YXJlIHRvIGhhdmUgZWRnZSBsZW5ndGggJDAkLCB0aHVzIGNvdmVyaW5nIGp1c3QgYSBzaW5nbGUgcG9pbnQuPFwvcD5cclxuXHJcbjxwPkZpbmQgYSBjb2xvcmZ1bCBzcXVhcmUgd2l0aCB0aGUgbWluaW11bSBzaWRlIGxlbmd0aCwgYW5kIHByaW50IHRoYXQgbGVuZ3RoLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdHdvIGludGVnZXJzICROJCBhbmQgJEskICgkMiBcXGxlIE4gXFxsZSAxMF41JCwgJDIgXFxsZSBLIFxcbGUgTiQpLjxcL3A+XHJcblxyXG48cD5UaGVuICROJCBsaW5lcyBmb2xsb3cuIFRoZSAkaSQtdGggb2YgdGhlc2UgbGluZXMgY29udGFpbnMgdGhyZWUgaW50ZWdlcnMsICR4X2kkLCAkeV9pJCwgYW5kICRjX2kkOiB0aGUgY29vcmRpbmF0ZXMgb2YgdGhlICRpJC10aCBwb2ludCBhbmQgaXRzIGNvbG9yLCByZXNwZWN0aXZlbHkgKCQxIFxcbGUgeF9pLCB5X2kgXFxsZSAyLjUgXFxjZG90IDEwXjUkLCAkMSBcXGxlIGNfaSBcXGxlIEskKS4gWW91IG1heSBhc3N1bWUgdGhhdCB0aGVyZSBpcyBhdCBsZWFzdCBvbmUgcG9pbnQgZm9yIGVhY2ggb2YgJGskIGNvbG9ycy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5QcmludCBvbmUgaW50ZWdlcjogdGhlIGFuc3dlciB0byB0aGUgcHJvYmxlbS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIiwic3VidGFzazEiOiIiLCJzdWJ0YXNrMiI6IiIsInN1YnRhc2szIjoiIiwic3VidGFzazQiOiIiLCJzdWJ0YXNrNSI6IiIsInN1YnRhc2s2IjoiIiwic3VidGFzazciOiIiLCJzdWJ0YXNrOCI6IiJ9XQ==

채점 및 기타 정보

  • 예제는 채점하지 않는다.