<|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

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

Generate all alternative versions of the text where exactly one negation is applied in exactly one position:

- Insert `not` (exactly lowercase) after any word equal (case-insensitive) to: `can`, `may`, `must`, `should`.
- Insert `no` (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: integer `k` (count), then `k` lines each containing one original sentence with exactly one negation applied. Order: sentence by sentence, within each sentence 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.
- Trigger words are matched case-insensitively, but 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 entire input: concatenate lines with single spaces to avoid word merging across line breaks.

2. Split text into sentences by scanning character-by-character: every `.` ends the current sentence.

3. For each sentence, split into words. Scan each position `i`:
   - If `words[i]` (lowercased) is one of `{can, may, must, should}`: create a new sentence inserting `"not"` after position `i`.
   - If `words[i]` (lowercased) is one of `{is, are}`: create a new sentence inserting `"no"` after position `i`, and if the next word is `a` or `the`, skip it.

4. Output count, then each variant as words separated by spaces with `.` at end.

Complexity is tiny: input ≤ 1024 bytes, O(total_words) time and memory.

---

## 4) C++ implementation

```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

string text;

string lower(const string& s) {
    string res;
    for(char c: s) {
        res += tolower(c);
    }
    return res;
}

vector<string> split_words(const string& s) {
    istringstream is(s);
    vector<string> res;
    string w;
    while(is >> w) {
        res.push_back(w);
    }
    return res;
}

void read() {
    string line;
    while(getline(cin, line)) {
        if(!text.empty() && text.back() != ' ') {
            text += ' ';
        }
        text += line;
    }
}

void solve() {
    // This is a fairly simple problem, with a somewhat convoluted problem
    // statement. We simply split the text into sentences by '.', for each
    // sentence find words matching "can/may/must/should" (insert "not") or
    // "is/are" (insert "no" and remove following "a/the" if that's the case).
    // Then we can just output all candidates.

    auto is_not_word = [](const string& s) {
        string lo = lower(s);
        return lo == "can" || lo == "may" || lo == "must" || lo == "should";
    };
    auto is_no_word = [](const string& s) {
        string lo = lower(s);
        return lo == "is" || lo == "are";
    };
    auto is_a_or_the = [](const string& s) {
        string lo = lower(s);
        return lo == "a" || lo == "the";
    };

    vector<string> sentences;
    string cur;
    for(char c: text) {
        if(c == '.') {
            sentences.push_back(cur);
            cur.clear();
        } else {
            cur += c;
        }
    }

    vector<vector<string>> results;
    for(auto& sent: sentences) {
        auto words = split_words(sent);
        int n = words.size();
        for(int i = 0; i < n; i++) {
            if(!is_not_word(words[i]) && !is_no_word(words[i])) {
                continue;
            }

            vector<string> out(words.begin(), words.begin() + i + 1);
            bool no = is_no_word(words[i]);
            out.push_back(no ? "no" : "not");
            int start = i + 1;
            start += (no && start < n && is_a_or_the(words[start]));
            out.insert(out.end(), words.begin() + start, words.end());
            results.push_back(out);
        }
    }

    cout << results.size() << '\n';
    for(auto& r: results) {
        for(int i = 0; i < (int)r.size(); i++) {
            cout << r[i];
            if(i + 1 == (int)r.size()) {
                cout << '.';
            } else {
                cout << ' ';
            }
        }
        cout << '\n';
    }
}

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

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}
```

---

## 5) Python implementation

```python
import sys


def solve() -> None:
    lines = sys.stdin.read().splitlines()
    text = " ".join(lines)

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

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

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

    sentences = []
    cur = []
    for ch in text:
        if ch == ".":
            sentences.append("".join(cur))
            cur = []
        else:
            cur.append(ch)

    results = []

    for sent in sentences:
        words = sent.split()
        n = len(words)

        for i in range(n):
            if not (is_not_word(words[i]) or is_no_word(words[i])):
                continue

            out = words[: i + 1]

            if is_no_word(words[i]):
                out.append("no")
                start = i + 1
                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)

    sys.stdout.write(str(len(results)) + "\n")
    for words in results:
        sys.stdout.write(" ".join(words) + ".\n")


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