+ **Time limit:** 1 second + **Memory limit:** 256 MB Each CodeStar fan has gifted a phone number to the bootcamp. We want to store all these phone numbers, but the problem is that each number is written in a different format, and we need to store them in a uniform way. Each gifted phone number falls into one of the following categories: + **Category 1:** starts with `09` and exactly 11 digits. + **Category 2:** starts with `98` and exactly 12 digits. + **Category 3:** starts with `+98`and exactly 12 digits. + Numbers that are **invalid**. You are asked to convert all valid gifted phone numbers to **Category 3 format** so that we can store them easily. A number is considered valid if it belongs to one of Categories 1–3. # Input The first line of input contains a natural number $n$. Then, each of the next $n$ lines contains a string $s$ representing a gifted phone number. It is guaranteed that each string contains only digits and the `+` character. # Output Your output should contain $n$ lines. For each line, if the corresponding phone number is valid, print it in **Category 3 format**; otherwise, print `invalid`. # Examples ## Sample Input 1 ``` 5 09123456789 0912345678+9 +989123456789 091234567891 989123456789 ``` ## Sample Output 1 ``` +989123456789 invalid +989123456789 invalid +989123456789 ``` **Explanation:** + `09123456789` is valid and in Category 1; it should be converted to Category 3 format: `+989123456789`. + `0912345678+9` has a `+` in the middle of digits, so it is invalid. + `+989123456789` is already in correct Category 3 format. + `091234567891` has one extra digit, so it is invalid. + `989123456789` is valid in Category 2 and should be converted to Category 3 format: `+989123456789`.

+ **Time limit:** 1 second + **Memory limit:** 256 MB Grandmother wants to grow **sprouted greens**. She has set aside $k$ lentil seeds and prepared a tray with $n$ suitable positions for the seeds. The positions are numbered from left to right from $1$ to $n$. The seeds must be planted with proper spacing, and each position can hold at most one seed. |  | |:---------------------------------------------------------------:| | Sabzeh symbolizes vitality and growth. | If two seeds are planted in consecutive positions, their growth will be hindered. Grandmother wants to place $k$ seeds in $n$ positions so that the number of such consecutive pairs is minimized. In other words, she wants to plant the seeds so that the number of integers $i$ with $1 \leq i \leq n-1$ for which both positions $i$ and $i+1$ have seeds is as small as possible. Grandmother needs your help to calculate this minimum number. # Input The first line contains two integers $n$ and $k$, respectively. # Output Print a single line containing the **minimum number of consecutive position pairs** that have seeds in both positions. # Examples ## Sample Input 1 ``` 5 2 ``` ## Sample Output 1 ``` 0 ``` **Explanation:** Grandmother can plant her two seeds in positions 1 and 4. No two seeds are adjacent. ## Sample Input 2 ``` 5 4 ``` ## Sample Output 2 ``` 2 ``` **Explanation:** Grandmother can plant her four seeds in positions 1, 2, 3, and 5. The adjacent pairs are $(1,2)$ and $(2,3)$, so the minimum number of consecutive pairs with seeds is 2.