<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

432. XYZX 2009
Time limit per test: 0.25 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard



The annual XYZX programming competition is well known for its unusual problem statements. The Technical Coordinator of the competition, also known as Snusmumrik, intentionally leaves some freedom in the problem statements, so that the participants have to guess the missing conditions from the sample tests, from the problem preface or even epigraph, or just invent something themselves. This peculiarity revealed itself in the latest XYZX-2009 competition as well.

Misha is competing in a round of that competition — Quarterfinal of Eniseysk, and he has bumped into that obstacle again: he needs to understand why does his perfectly correct program fail on the sample tests. The statements are in English, and he knows that there is only one false sentence in the whole problem statement. Moreover, he knows a set of rules that enables him to restore the original statement that the author had in mind. It is very simple: the word "not" can be inserted after any of the words "can", "may", "must", "should" in the text; also the word "no" can be inserted after any of the phrases "is", "are". Words "not" and "no" must be inserted exactly as written: "Not", "nO" and other variants are not permitted. The other words mentioned, however, are case insensitive, so you can insert "not" after "Can", and you can insert "no" after "ARE". If there is any article ("a" or "the") after "is" or "are" where you're inserting "no", you must also remove that article.

Misha wants to get the list of all the possible reasons that his program doesn't work on the sample tests. A reason here is a sentence where a negation can be applied. Remember that no two negations can be applied simultaneously, neither in one sentence nor in different sentences.

Input
The input file contains the text of the problem statement containing latin letters, single spaces and dots. Every sentence has a dot at the end (which is not considered the part of the last word). Words are separated with a single space. There is no space before any dot. There is exactly one space after each dot unless that dot follows the last sentence; in that case, the dot is followed by a newline, and then the input file ends. When inserting a word "not" or "no" after some word, you must first insert a single space, then the corresponding word immediately. The size of the input file doesn't exceed 1024 bytes.

Output
The output file must first contain an integer k on a line by itself — the number of ways the problem statement can be understood differently. Then k lines must follow. Each line should contain one sentence from the initial text with exactly one negation applied. You must list all the possibilities (the lines are wrapped in the sample output just for better visibility; you must output one sentence per line). All the variants of negation must go in the natural order: all the negations that can be inserted in the first sentence, then all the negations that can be inserted in the second sentence, etc. Inside one sentence, first goes the negation that is applied after the first word (if applicable), then the one that is applied after the second word, etc.

You must not change the case of the letters in the words that you copy from the initial sentences. Your words must still be separated with single spaces, and the same rules apply to the dots at the ends of the sentences, as they do for the input sentences.

Example(s)
sample input
sample output
There is a field with label K on the field. There is a field
with label G on the field. You must intersect the rectangle
with each of the given rectangles separately. Two different
particles can annihilate each other in case of collision.
There must be a blank line after each test case output. Two
different ways to insert a symbol into the expression are
considered the same if the resulting expressions viewed as
strings are equal. Misha can find out whether this problem
statement can be understood correctly at all.
9
There is no field with label K on the field.
There is no field with label G on the field.
You must not intersect the rectangle with each of the given
rectangles separately.
Two different particles can not annihilate each other in
case of collision.
There must not be a blank line after each test case output.
Two different ways to insert a symbol into the expression
are no considered the same if the resulting expressions
viewed as strings are equal. Two different ways to insert
a symbol into the expression are considered the same if
the resulting expressions viewed as strings are no equal.
Misha can not find out whether this problem statement
can be understood correctly at all.
Misha can find out whether this problem statement
can not be understood correctly at all.

<|response|>
## 1) Abridged problem statement (concise)

You are given a text consisting of sentences ending with a dot `.`. Words use only latin letters, are separated by single spaces, and there is no space before a dot.

You must generate all alternative versions of the text where **exactly one negation** is applied in **exactly one** position:

- Insert the word **`not`** (must be exactly lowercase) after any word equal (case-insensitive) to:  
  `can`, `may`, `must`, `should`
- Insert the word **`no`** (must be exactly lowercase) after any word equal (case-insensitive) to:  
  `is`, `are`  
  Additionally, if the next word is an article `a` or `the` (case-insensitive), it must be **removed**.

Output:
1) integer `k` — number of possible single-negation sentences  
2) then `k` lines: each is one original sentence with exactly one negation applied.

Order: sentence-by-sentence, and inside a sentence from left to right.

---

## 2) Key observations

- We never apply two negations at once, so every output line is derived from **one sentence** and **one insertion position**.
- The triggers are matched **case-insensitively**, but all original words must be copied **with original casing**.
- The inserted words must be exactly `"not"` or `"no"` (lowercase).
- For `is/are → "no"`: optionally remove the following article `a/the` (case-insensitive).
- Input can contain line breaks (wrapping), but logically it is one stream; easiest is to read the whole file and treat it as one string.
- Sentence boundaries are exactly at dots `.`; the dot is not part of the last word and must be re-added on output.

---

## 3) Full solution approach

1. **Read the entire input**
   - Read all lines to EOF.
   - Concatenate them with single spaces between lines (to avoid accidental word merging).

2. **Split text into sentences**
   - Scan the concatenated text character-by-character.
   - Every time you see `.`, you finish the current sentence and store it (without the dot).

3. **Process each sentence**
   - Split sentence into `words[]` by spaces.
   - For each position `i`:
     - If `words[i]` (lowercased) is one of `{can, may, must, should}`:
       - Create a new sentence: insert `"not"` after `words[i]`.
     - If `words[i]` (lowercased) is one of `{is, are}`:
       - Create a new sentence: insert `"no"` after `words[i]`.
       - If the next word exists and is `a` or `the` (lowercased), skip it (remove article).
   - Collect every generated variant in the required order (scan left to right, sentence by sentence).

4. **Output**
   - Print number of generated variants.
   - For each variant, print words joined by single spaces and a dot at the end.

Complexity is tiny: input ≤ 1024 bytes, so `O(total_words)` time and memory is more than enough.

---

## 4) C++ implementation (detailed comments)

```cpp
#include <bits/stdc++.h>
using namespace std;

// Convert a word to lowercase for case-insensitive comparisons.
// Input guarantees latin letters only, so ASCII tolower is enough.
static string to_lower_ascii(const string& s) {
    string t = s;
    for (char& c : t) c = (char)tolower((unsigned char)c);
    return t;
}

// Split a sentence (no dots) into words by whitespace.
static vector<string> split_words(const string& s) {
    istringstream in(s);
    vector<string> w;
    string x;
    while (in >> x) w.push_back(x);
    return w;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 1) Read entire input (may contain newlines due to wrapping).
    //    We'll join lines with single spaces.
    string text, line;
    bool firstLine = true;
    while (getline(cin, line)) {
        if (!firstLine) text.push_back(' ');
        firstLine = false;
        text += line;
    }

    // Helper predicates for trigger words.
    auto is_not_trigger = [&](const string& w) {
        string lo = to_lower_ascii(w);
        return lo == "can" || lo == "may" || lo == "must" || lo == "should";
    };
    auto is_no_trigger = [&](const string& w) {
        string lo = to_lower_ascii(w);
        return lo == "is" || lo == "are";
    };
    auto is_article = [&](const string& w) {
        string lo = to_lower_ascii(w);
        return lo == "a" || lo == "the";
    };

    // 2) Split into sentences by '.'
    //    The dot is not part of the sentence content we store.
    vector<string> sentences;
    string cur;
    for (char c : text) {
        if (c == '.') {
            sentences.push_back(cur);
            cur.clear();
        } else {
            cur.push_back(c);
        }
    }

    // 3) Generate all possible single-negation variants in required order.
    vector<vector<string>> results;

    for (const string& sent : sentences) {
        vector<string> words = split_words(sent);
        int n = (int)words.size();

        for (int i = 0; i < n; i++) {
            bool can_insert_not = is_not_trigger(words[i]);
            bool can_insert_no  = is_no_trigger(words[i]);
            if (!can_insert_not && !can_insert_no) continue;

            // Start building the output sentence:
            // copy words[0..i] as-is (preserving original casing)
            vector<string> out(words.begin(), words.begin() + i + 1);

            if (can_insert_no) {
                // Insert "no" after is/are
                out.push_back("no");

                // Then copy the remainder, possibly skipping an article
                int start = i + 1;
                if (start < n && is_article(words[start])) start++;
                out.insert(out.end(), words.begin() + start, words.end());
            } else {
                // Insert "not" after can/may/must/should
                out.push_back("not");
                out.insert(out.end(), words.begin() + (i + 1), words.end());
            }

            results.push_back(std::move(out));
        }
    }

    // 4) Output.
    cout << results.size() << "\n";
    for (const auto& r : results) {
        for (int i = 0; i < (int)r.size(); i++) {
            if (i) cout << ' ';
            cout << r[i];
        }
        cout << ".\n";
    }

    return 0;
}
```

---

## 5) Python implementation (detailed comments)

```python
import sys

def solve() -> None:
    # 1) Read entire input. Lines may be wrapped; we join with spaces.
    lines = sys.stdin.read().splitlines()
    text = " ".join(lines)

    def is_not_trigger(w: str) -> bool:
        return w.lower() in ("can", "may", "must", "should")

    def is_no_trigger(w: str) -> bool:
        return w.lower() in ("is", "are")

    def is_article(w: str) -> bool:
        return w.lower() in ("a", "the")

    # 2) Split into sentences by '.'
    #    Store each sentence without the dot; later re-add '.' on output.
    sentences = []
    cur = []
    for ch in text:
        if ch == ".":
            sentences.append("".join(cur))
            cur = []
        else:
            cur.append(ch)

    results: list[list[str]] = []

    # 3) For each sentence, try inserting exactly one negation after each word.
    for sent in sentences:
        # Words are separated by single spaces in the statement,
        # but split() is safe here.
        words = sent.split()
        n = len(words)

        for i in range(n):
            if not (is_not_trigger(words[i]) or is_no_trigger(words[i])):
                continue

            out = words[: i + 1]  # copy up to and including i

            if is_no_trigger(words[i]):
                out.append("no")
                start = i + 1
                # Remove article immediately after is/are if present
                if start < n and is_article(words[start]):
                    start += 1
                out.extend(words[start:])
            else:
                out.append("not")
                out.extend(words[i + 1 :])

            results.append(out)

    # 4) Output count and all variants.
    sys.stdout.write(str(len(results)) + "\n")
    for wlist in results:
        sys.stdout.write(" ".join(wlist) + ".\n")

if __name__ == "__main__":
    solve()
```

