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

368. Tests
Time limit per test: 0.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



It is soon the exam time for entrants at Berland State University, in short BerSU. As usual, for every subject, instead of passing an entry exam, one can present the results of the centralized test on that subject. Knowing that, Peter had passed the tests for all of the M subjects in advance.

The selection committees of each of the N BerSU faculties have published the rules for automatic conversion of test results into exam grades, as well as the sum of the grades necessary to enter study for each of the S specialties. Peter is not very confident in his test results, so he made an application for every possible specialty of each of the BerSU faculties. Now, he is curious and wants to know which of his applications were accepted.

Input
In the first line of input file there are two integers N and M (1 ≤ N ≤ 100, 1 ≤ M ≤ 100) — the number of faculties and the number of subjects for which Peter passed the tests, respectively. Next line contains M integers B1, B2,..., BM (0 ≤ Bi ≤ 100); here, Bi is Peter's score for i-th subject. After that come N blocks for description of the faculties.

The first line of a block contains the name of the faculty; it can contain just uppercase and lowercase Latin letters and spaces and is no longer than 100 characters. The second line contains K — the number of exams one should pass in order to enter study for any specialty on that faculty, and after that K integers — the numbers of the subjects at these exams. The third line contains K triplets of numbers X1 < Y1 < Z1 X2 < Y2 < Z2... XK < YK < ZK; here, Xi, Yi and Zi have the following meaning. Suppose Peter has a score of T for the respective subject. If T < Xi, Peter gets a "2" for it; if the Xi ≤ T < Yi, he gets a "3"; if Yi ≤ T < Zi, a "4"; and finally, if Zi ≤ T, Peter gets a "5".

After these three lines of a block, there comes a line with a single integer S on it (1 ≤ S ≤ 100). Next are S sub-blocks describing specialties. Each of the blocks consists of two lines. First of them contains the name of the specialty. Second line contains a single integer — the sum of grades necessary to pass the exam. In order for Peter's application to be accepted, he should have the sum of grades no less than this number.

The names of faculties and specialties can contain just uppercase and lowercase Latin letters and spaces, can't start or end with a space and have length between 1 and 100 characters, inclusive.

Output
For each Peter's application that got accepted, output the names of the faculty and the specialty on a single line, separated by a single space. Lines can be output in any order.

If all Peter's applications were rejected, output the word "Army" on the first line of the input file.

Example(s)
sample input
sample output
2 3
98 87 90
Computer Science and IT
3 1 2 3
90 95 99 80 90 100 91 93 95
2
Computer Security
15
Applied Math and Informatics
14
Mathematics and Mechanics
3 1 2 3
70 80 90 80 85 90 65 76 90
2
Applied Math and Informatics
13
Applied Math in Agriculture
5
Mathematics and Mechanics Applied Math and Informatics
Mathematics and Mechanics Applied Math in Agriculture

sample input
sample output
1 3
98 87 90
Computer Science and IT
3 1 2 3
90 95 99 80 90 100 91 93 95
1
Computer Security
15
Army

<|response|>
## 1. Abridged problem statement

Peter has test scores for `M` subjects. There are `N` faculties. Each faculty:

- has a name,
- requires `K` subjects,
- gives threshold rules to convert Peter’s test score in each required subject into an exam grade `2`, `3`, `4`, or `5`,
- has several specialties, each with a minimum required sum of grades.

Peter applied to every specialty of every faculty.

For every accepted application, output:

```text
FacultyName SpecialtyName
```

If none are accepted, output:

```text
Army
```

Faculty and specialty names may contain spaces, so they must be read as whole lines.

---

## 2. Key observations needed to solve the problem

1. **Each faculty has its own grading rules.**
   The same test score can become different grades in different faculties.

2. **For one faculty, Peter’s total grade sum is fixed.**
   Once we calculate the sum of grades for that faculty, we can compare it with every specialty requirement of that faculty.

3. **Grade conversion is direct.**
   For a subject score `T` and thresholds `X < Y < Z`:

   ```text
   T < X       -> grade 2
   X <= T < Y  -> grade 3
   Y <= T < Z  -> grade 4
   Z <= T      -> grade 5
   ```

4. **Input parsing is the main tricky part.**
   Faculty names and specialty names may contain spaces, so we cannot read them using ordinary token-based input like `cin >> name`.
   We need to use `getline` in C++ or full-line reading in Python.

5. **Constraints are small.**
   `N, M, S <= 100`, so a straightforward simulation is easily fast enough.

---

## 3. Full solution approach based on the observations

For each faculty:

1. Read the faculty name.
2. Read `K` and the `K` subject indices.
3. Read `K` triples of thresholds.
4. Calculate Peter’s total grade sum for this faculty:
   - For each required subject:
     - get Peter’s score for that subject,
     - compare it with the corresponding thresholds,
     - add the resulting grade to the total.
5. Read the number of specialties `S`.
6. For each specialty:
   - read the specialty name,
   - read the required sum,
   - if Peter’s total sum for the faculty is at least this required sum, store the output line.

After processing all faculties:

- If there is at least one accepted application, print all stored lines.
- Otherwise, print `Army`.

### Complexity

Let:

- `N` be the number of faculties,
- `M` be the number of subjects,
- `S` be the maximum number of specialties per faculty.

For each faculty, we process its required subjects and its specialties.

Time complexity:

```text
O(total required subjects + total specialties)
```

In the worst case, this is roughly:

```text
O(N * (M + S))
```

Memory complexity:

```text
O(number of accepted applications)
```

We can process the input faculty by faculty without storing all faculty data.

---

## 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;
};

struct specialty {
    string name;
    int required;
};

struct faculty {
    string name;
    int k;
    vector<int> subjects;
    vector<tuple<int, int, int>> thresholds;
    vector<specialty> specs;
};

int n, m;
vector<int> scores;
vector<faculty> faculties;

void read() {
    cin >> n >> m;
    scores.assign(m, 0);
    cin >> scores;

    faculties.assign(n, {});
    for(auto& f: faculties) {
        cin >> ws;
        getline(cin, f.name);
        cin >> f.k;
        f.subjects.assign(f.k, 0);
        cin >> f.subjects;
        f.thresholds.assign(f.k, {});
        for(auto& [x, y, z]: f.thresholds) {
            cin >> x >> y >> z;
        }

        int s;
        cin >> s;
        f.specs.assign(s, {});
        for(auto& sp: f.specs) {
            cin >> ws;
            getline(cin, sp.name);
            cin >> sp.required;
        }
    }
}

void solve() {
    // Pure implementation. For each faculty we look up Peter's score on
    // every required subject, convert it to a 2/3/4/5 grade via the
    // X<Y<Z thresholds, sum the grades, and accept every specialty whose
    // required sum is at most that total. The only mildly fiddly part is
    // the parsing, since faculty and specialty names can contain spaces,
    // so we read the input line by line.

    vector<string> accepted;
    for(const auto& f: faculties) {
        int total = 0;
        for(int j = 0; j < f.k; j++) {
            int t = scores[f.subjects[j] - 1];
            auto [x, y, z] = f.thresholds[j];
            int grade = t < x ? 2 : t < y ? 3 : t < z ? 4 : 5;
            total += grade;
        }
        for(const auto& sp: f.specs) {
            if(total >= sp.required) {
                accepted.push_back(f.name + ' ' + sp.name);
            }
        }
    }

    if(accepted.empty()) {
        cout << "Army\n";
    } else {
        for(const auto& line: accepted) {
            cout << line << '\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 with detailed comments

```python
import sys


def main():
    # Read all input lines.
    # We use splitlines() to preserve names with spaces as full lines.
    lines = sys.stdin.read().splitlines()

    idx = 0

    # First line: number of faculties and number of subjects.
    n, m = map(int, lines[idx].split())
    idx += 1

    # Second line: Peter's scores for all subjects.
    scores = list(map(int, lines[idx].split()))
    idx += 1

    accepted = []

    # Process every faculty.
    for _ in range(n):
        # Faculty name may contain spaces, so take the entire line.
        faculty_name = lines[idx]
        idx += 1

        # Next line: K followed by K subject indices.
        data = list(map(int, lines[idx].split()))
        idx += 1

        k = data[0]
        subjects = data[1:]

        # Next line contains 3 * K integers:
        # X1 Y1 Z1 X2 Y2 Z2 ...
        threshold_values = list(map(int, lines[idx].split()))
        idx += 1

        thresholds = []
        for i in range(k):
            x = threshold_values[3 * i]
            y = threshold_values[3 * i + 1]
            z = threshold_values[3 * i + 2]
            thresholds.append((x, y, z))

        # Compute Peter's total grade sum for this faculty.
        total_grade = 0

        for i in range(k):
            # Subject numbers are 1-based in the input.
            subject_index = subjects[i] - 1

            t = scores[subject_index]
            x, y, z = thresholds[i]

            if t < x:
                grade = 2
            elif t < y:
                grade = 3
            elif t < z:
                grade = 4
            else:
                grade = 5

            total_grade += grade

        # Number of specialties.
        s = int(lines[idx])
        idx += 1

        # Process each specialty.
        for _ in range(s):
            # Specialty name may also contain spaces.
            specialty_name = lines[idx]
            idx += 1

            required_sum = int(lines[idx])
            idx += 1

            if total_grade >= required_sum:
                accepted.append(f"{faculty_name} {specialty_name}")

    # Output answer.
    if accepted:
        print("\n".join(accepted))
    else:
        print("Army")


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