# Bài 2: Gen nổi trội

Giáo sư Strange đang tham gia vào [Dự án Bản đồ gen Người](https://vi.wikipedia.org/wiki/D%E1%BB%B1_%C3%A1n_b%E1%BA%A3n_%C4%91%E1%BB%93_gen_ng%C6%B0%E1%BB%9Di) ([Human Genome Project - HGP](https://en.wikipedia.org/wiki/Human_Genome_Project)). Ngài ấy muốn tìm ra những đặc điểm nổi trội nhất của dãy DNA được nghiên cứu. Một "đặc điểm nội trội" có thể giải mã được thành một xâu con liên tiếp trong dãy DNA được xuất hiện ít nhất là hai lần. Một đặc điểm $s_1$ được xem là nổi trội hơn đặc điểm $s_2$ khi độ dài của dãy DNA cấu tạo nên $s_1$ lớn hơn $s_2$ ($|s_1| > |s_2|$).
Hãy giúp Giáo sư Strange tìm dãy DNA của đặc điểm nội trội nhất trong một dãy DNA rất dài. Nếu có nhiều kết quả thỏa mãn, trả về kết quả đầu tiên.

## Đầu vào
- Gồm một dòng duy nhất chứa xâu $s$ ($|s| \le 10^5$) chỉ gồm các kí tự 'A', 'T', 'G', 'C' là dãy DNA cần tìm đặc điểm nổi trội nhất.
## Đầu ra
- Gồm một dòng duy nhất là kết quả của bài toán.

## Test case 1

| Input | Output |
| --------- | ------- |
| ATATA | ATA |
- Giải thích ví dụ: xâu 'ATA' lặp lại 2 lần trong dãy DNA được cho. Đây cũng là xâu con dài nhất lặp lại nhiều lần.

## Test case 2

| Input | Output |
| -------- | -------- |
| AATTC | A |
- Giải thích ví dụ: xâu 'A' được lặp lại 2 lần trong dãy DNA được cho. Ngoài ra còn có xâu 'T' được lặp lại 2 lần, nhưng xâu 'T' xuất hiện sau lần xuất hiện đầu tiên của xâu 'A' nên kết quả là xâu 'A'.