122B.md (1899B)
1 Source: https://codeforces.com/problemset/problem/122/B 2 3 B. Lucky Substring 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 stdin 16 17 output 18 19 stdout 20 21 Petya loves lucky numbers. Everybody knows that lucky numbers are positive integers whose decimal representation contains only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not. 22 23 One day Petya was delivered a string *s*, containing only digits. He needs to find a string that 24 25 * represents a lucky number without leading zeroes, 26 * is not empty, 27 * is contained in *s* as a substring the maximum number of times. 28 29 Among all the strings for which the three conditions given above are fulfilled, Petya only needs the lexicographically minimum one. Find this string for Petya. 30 31 Input 32 33 The single line contains a non-empty string *s* whose length can range from 1 to 50, inclusive. The string only contains digits. The string can contain leading zeroes. 34 35 Output 36 37 In the only line print the answer to Petya's problem. If the sought string does not exist, print "-1" (without quotes). 38 39 Examples 40 41 Input 42 43 ``` 44 047 45 ``` 46 47 Output 48 49 ``` 50 4 51 ``` 52 53 Input 54 55 ``` 56 16 57 ``` 58 59 Output 60 61 ``` 62 -1 63 ``` 64 65 Input 66 67 ``` 68 472747 69 ``` 70 71 Output 72 73 ``` 74 7 75 ``` 76 77 Note 78 79 The lexicographical comparison of strings is performed by the < operator in the modern programming languages. String *x* is lexicographically less than string *y* either if *x* is a prefix of *y*, or exists such *i* (1 ≤ *i* ≤ *min*(|*x*|, |*y*|)), that *x**i* < *y**i* and for any *j* (1 ≤ *j* < *i*) *x**j* = *y**j*. Here |*a*| denotes the length of string *a*. 80 81 In the first sample three conditions are fulfilled for strings "4", "7" and "47". The lexicographically minimum one is "4". 82 83 In the second sample *s* has no substrings which are lucky numbers. 84 85 In the third sample the three conditions are only fulfilled for string "7".