Combination Lock

AtCoder

IDcf17_final_e

Time2000ms

Memory256MB

Difficulty—

Ringo has a string $S$. He can perform the following $N$ kinds of operations any number of times in any order. * Operation $i$: For each of the characters from the $L_i$\-th through the $R_i$\-th characters in $S$, replace it with its succeeding letter in the English alphabet. (That is, replace `a` with `b`, replace `b` with `c` and so on.) For `z`, we assume that its succeeding letter is `a`. Ringo loves palindromes and wants to turn $S$ into a palindrome. Determine whether this is possible. ## Constraints * $1 \leq |S| \leq 10^5$ * $S$ consists of lowercase English letters. * $1 \leq N \leq 10^5$ * $1 \leq L_i \leq R_i \leq |S|$ ## Input Input is given from Standard Input in the following format: $S$ $N$ $L_1$ $R_1$ $L_2$ $R_2$ $:$ $L_N$ $R_N$ [samples]

Samples

Input #1

bixzja
2
2 3
3 6

Output #1

YES

For example, if we perform Operation $1$, $2$ and $1$ in this order, $S$ changes as `bixzja` → `bjyzja` → `bjzakb` → `bkaakb` and becomes a palindrome.

Input #2

abc
1
2 2

Output #2

NO

Input #3

cassert
4
1 2
3 4
1 1
2 2

Output #3

YES

API Response (JSON)

{
  "problem": {
    "name": "Combination Lock",
    "description": {
      "content": "Ringo has a string $S$. He can perform the following $N$ kinds of operations any number of times in any order. *   Operation $i$: For each of the characters from the $L_i$\\-th through the $R_i$\\-th c",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "cf17_final_e"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Ringo has a string $S$.\nHe can perform the following $N$ kinds of operations any number of times in any order.\n\n*   Operation $i$: For each of the characters from the $L_i$\\-th through the $R_i$\\-th c...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments