A **palindrome** is a positive integer whose decimal representation reads the same forwards and backwards, with no leading zeros. For example, `7`, `44`, `121`, and `3773` are palindromes; `10` and `120` are not. Given a positive integer `K`, return the smallest palindrome that is **strictly greater** than `K`. ## Examples **Example 1** ``` Input: K = 123 Output: 131 ``` The palindromes near 123 are 121 and 131; the smallest one strictly greater than 123 is 131. **Example 2** ``` Input: K = 99 Output: 101 ``` 99 is itself a palindrome, but the answer must be strictly greater than K, and 100 is not a palindrome. **Example 3** ``` Input: K = 131 Output: 141 ``` **Example 4** ``` Input: K = 12932 Output: 13031 ``` Mirroring the left half of 12932 gives 12921, which is too small, so the middle must be incremented before mirroring. **Example 5** ``` Input: K = 9999 Output: 10001 ``` When K consists of all 9s, the answer has one more digit. ## Constraints - `1 <= K < 10^18` (fits in a signed 64-bit integer, and so does the answer) - Your solution should run in time proportional to the number of digits of `K` (up to a small polynomial factor). Incrementing and re-checking one number at a time is too slow: consecutive palindromes near `10^18` can be roughly `10^9` apart. ## Output Return the answer as an integer.