solved.ac Grand Arena #3

In this problem, we need to calculate the number of bundles of T-shirts of each size, and the number of bundles of pens that we need to order. First, let's look at how we can find the number of bundles of pens as this is simpler.

## Pens

To find how many bundles of pens we should order, we need to group the $N$ pens in bundles of $P$. By dividing $N$ by $P$, we can get the quotient $q$ and remainder $r$. As a mathematical expression, we can denote this as $N \div P = q \cdots r$. This means by grouping the pens in bundles of $P$, we get $q$ complete bundles and $r$ remaining. These $q, r$ values are the number of bundles of pens that we need to order, and the number of pens we need to order one by one, respectively.

## T-Shirts

### Solution 1

Now let's find the number of  bundles of T-shirts of size S that we need to buy.

We use division again to group T-shirts of size $S$ in bundles of $T$. Let's call the quotient and remainder of this division $q, r$ respectively. $(S \div T = q \cdots r)$

- If $r = 0$, we can distribute T-shirts without any leftovers by ordering exactly $q$ bundles. The answer is $q$.

- If $r > 0$, $r$ more T-shirts must be ordered after ordering $q$ bundles. Since T-shirts cannot be ordered one by one, we need to order one more bundle. Thus, the answer is $q+1$. 

This can be implemented as follows in the following languages. Variable names are `S, T` respectively, and the answer is `res` .

### C++

```C++
int q = S / T, r = S % T;
int res = q + (r > 0 ? 1 : 0);
```

### Python

```python
q, r = S // T, S % T
res = q + (1 if r > 0 else 0)
```

### Rust

```rust
let q = S / T;
let r = S % T;
let res = q + if r > 0 { 1 } else { 0 };
```

### Solution 2

We can write the code without using `if` statements too. First let's define the following symbols.

- $\frac{a}{b}$: The value of $a$ divided by $b$.
  - Here we use the division between real numbers instead of between integers.
  - For example, $\frac{9}{5} = 1.8$.
- $\left \lfloor x \right \rfloor, \left \lceil x \right \rceil$: The largest integer smaller than or equal to $x$, and the smallest integer larger than or equal to $x$, respectively.
  - For example, $\lfloor 3 \rfloor = 3, \lfloor 3.14 \rfloor = 3, \lfloor 4 \rfloor = 4$.
  - For example, $\lceil 3 \rceil = 3, \lceil 3.14 \rceil = 4, \lceil 4 \rceil = 4$.
  - If $x$ is an integer , $\left \lceil x \right \rceil = \left \lfloor x \right \rfloor$.
  - If $x$ is not an integer, $\left \lceil x \right \rceil = \left \lfloor x \right \rfloor + 1$. 

The quotient in the integer division of $S$ by $T$ is $\left\lfloor \frac{S}{T} \right \rfloor$. After dividing $S$ by $T$, this is obtained by removing the fractional part that we cannot group in bundles of $T$. However, we need to find $\left \lceil \frac{S}{T} \right \rceil$ in this problem. Even if there is a fractional part remaining, we need to think of it as $1$ complete bundle. 

Now, let's prove the following. For an integer $S$ greater than or equal to $0$, and an integer $T$ greater than or equal to $1$, $\left\lceil \frac{S}{T} \right\rceil = \left\lfloor \frac{S+T-1}{T} \right\rfloor$.

- If $S$ is a multiple of $T$, $\left\lceil \frac{S}{T} \right\rceil = \frac{S}{T}$, and $\left\lfloor \frac{S+T-1}{T} \right\rfloor = \left\lfloor \frac{S}{T} + \frac{T-1}{T} \right\rfloor$. Since $\frac{S}{T}$ is an integer, and $\frac{T-1}{T}$ is ignored as it is smaller than $1$, $\left\lfloor \frac{S+T-1}{T} \right\rfloor = \frac{S}{T}$.

- If $S$ is not a multiple of $T$, $\frac{S}{T}$ is not an integer, so $\left\lceil \frac{S}{T} \right\rceil = \left\lfloor \frac S T \right\rfloor + 1$. Furthermore, since there is at least $1$ remainder from $S$, we get the same quotient when dividing $S-1$ by $T$. That is, $\left \lfloor \frac{S-1}{T} \right \rfloor = \left \lfloor \frac{S}{T} \right\rfloor$. $\left\lfloor \frac{S+T-1}{T} \right\rfloor = \left\lfloor \frac{S-1}{T} + \frac{T}{T} \right\rfloor = \left\lfloor \frac{S}{T} \right \rfloor + 1 = \left\lceil \frac S T \right \rceil$.

We can make our code much simpler using this method. Below are example solutions written in each language.

### Code (C++)

```cpp
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int N;
    cin >> N;
    vector<int> sizes(6);
    for (int &size : sizes)
        cin >> size;
    int T, P;
    cin >> T >> P;
    int sumv = 0;
    for (int size : sizes)
        sumv += (size + T - 1) / T;
    cout << sumv << endl;
    cout << N / P << " " << N % P << endl;
}
```

### Code (Python)

```python
def main():
    N = int(input())
    sizes = list(map(int, input().split()))
    T, P = map(int, input().split())
    print(sum((size + T - 1) // T for size in sizes))
    print(N // P, N % P)


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

### Code (Rust)

```rust
use std::io::*;

fn main() {
    let n = read_vec()[0];
    let sizes = read_vec();
    let (t, p) = {
        let v = read_vec();
        (v[0], v[1])
    };

    println!("{}", sizes.iter().map(|x| (x + t - 1) / t).sum::<u32>());
    println!("{} {}", n / p, n % p);
}

fn read_vec() -> Vec<u32> {
    let mut s = String::new();
    stdin().read_line(&mut s).unwrap();
    s.split_whitespace().map(|x| x.parse().unwrap()).collect()
}
```

Let's denote the amount of water currently flowing out of the faucet as $A_i$. Let's also say if the $i$-th faucet is open, $B_i = 1$, and if it is closed, $B_i = 0$.  Now, each query and the answer that we need to find can be described as follows.

- Query $1, i, x$ means change $A_i$ to $x$.
- Query $2, i$ means if $B_i$ was $0$, change it to $1$, and if it was $1$, change it to $0$.

- The amount of water flowing into the tank from each faucet can be represented as $B_iA_i$. That is, if the faucet is open, the amount is $A_i$, and if the faucet is close, the amount is $B_i$. This problem is about finding $B_1A_1 + B_2A_2 + \cdots + B_NA_N$.

Let's use the fact that query operations on the $i$-th faucet only affect $B_iA_i$, and no other values. We will call the answer of the previous query $S$.

- The total amount of water flowing out of faucets excluding the $i$-th one can be calculated by subtracting $B_iA_i$ from the total. That is, $T = S-B_iA_i$. This value does not change before or after the query.
- By applying a query, $B_iA_i$ becomes $B'_i A'_i$.
- To find the total amount of water flowing out of all faucets, we add the amount of water flowing out of the $i$-th faucet. That is, the answer of this query is $S' = T + B'_iA'_i$.

### Code (C++)

```cpp
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin >> N;
    vector<int> A(N);
    vector<bool> B(N, true);
    int64_t S = 0;
    for (int &a : A)
        cin >> a, S += a;
    cout << S << '\n';
    int Q;
    cin >> Q;
    for (int q = 0; q < Q; q++)
    {
        int t, i;
        cin >> t >> i;
        i--;

        if (B[i])
            S -= A[i];

        if (t == 1)
        {
            int x;
            cin >> x;
            A[i] = x;
        }
        if (t == 2)
            B[i] = !B[i];

        if (B[i])
            S += A[i];
        cout << S << '\n';
    }
}
```

### Code (Python)

```python
import sys


def input(): return sys.stdin.readline().rstrip()


def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = [True]*N
    S = sum(A)
    print(S)

    Q = int(input())
    for _ in range(Q):
        qry = list(map(int, input().split()))
        (t, i) = (qry[0], qry[1]-1)

        if B[i]:
            S -= A[i]

        if t == 1:
            A[i] = qry[2]
        if t == 2:
            B[i] = not B[i]

        if B[i]:
            S += A[i]
        print(S)


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

### Code (Rust)

```rust
use std::{cell::*, fmt::Debug, io::*, str::*};

fn main() {
    let n = read_vec()[0];
    let mut a = read_vec();
    let mut b = vec![true; n];
    let mut ans = a.iter().sum::<u64>();
    println!("{}", ans);
    let q = read_vec()[0];
    for _ in 0..q {
        let q = read_vec();
        let t = q[0];
        let i = (q[1] - 1) as usize;
        if b[i] {
            ans -= a[i];
        }
        match t {
            1 => a[i] = q[2],
            2 => b[i] = !b[i],
            _ => panic!(),
        };
        if b[i] {
            ans += a[i];
        }
        println!("{}", ans);
    }
}

thread_local! {
    static STDIN: RefCell<StdinLock<'static>> = RefCell::new(stdin().lock());
    static STDOUT: RefCell<BufWriter<StdoutLock<'static>>> = RefCell::new(BufWriter::new(stdout().lock()));
}
fn read_vec<T: FromStr>() -> Vec<T>
where
    <T as FromStr>::Err: Debug,
{
    let mut s = String::new();
    STDIN.with(|cell| { cell.borrow_mut().read_line(&mut s).unwrap(); });
    s.split_whitespace().map(|x| x.parse().unwrap()).collect()
}
#[macro_export]
macro_rules! println {
    ($($t:tt)*) => {
        STDOUT.with(|cell| writeln!(cell.borrow_mut(), $($t)*).unwrap());
    };
}
```


## Solution 1

Let's decide on the two fruits that will be used. After that, we look for the longest continuous subsequence of those two fruits. This can be done by using the `split` method (if your language supports it) or by maintaining a `cnt` variable and traversing the list from the front. If the current element is one of the chosen types of fruits, add $1$ to `cnt` . Otherwise, reset `cnt` to $0$. Find the maximum possible `cnt` value.

Supposing there are $d = 9$ types of fruits, there are $\frac{d(d-1)}{2} = 36$ ways to choose two of them, and each of the choices $O(N)$ time. Total time complexity is $O(d^2N)$.

### Code (C++20)

```cpp
#include <iostream>
#include <ranges>
#include <vector>
using namespace std;

int main()
{
    int N;
    cin >> N;
    vector<int> S(N);
    for (int &s : S)
        cin >> s;
    int ans = 0;
    for (int i = 1; i <= 9; i++)
        for (int j = 1; j < i; j++)
        {
            auto v = S | views::transform([&](int x)
                                          { return x == i || x == j; });
            for (auto w : views::split(v, false))
                ans = max(ans, (int)distance(w.begin(), w.end()));
        }
    cout << ans << endl;
}
```

### Code (Python)

```python
import re


def main():
    input()
    s=''.join(input().split())
    ans = 0
    for i in range(1, 10):
        for j in range(1, i):
            ans = max(ans, max(map(len, re.split(f'[^{i}{j}]', s))))
    print(ans)


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

### Code (Rust)

```rust
use std::io::*;
use std::iter::FromIterator;

fn main() {
    stdin().read_line(&mut String::new()).unwrap();
    let mut s = String::new();
    stdin().read_line(&mut s).unwrap();
    let s = String::from_iter(s.chars().filter(|&x| !x.is_ascii_whitespace()));
    let mut ans = 0;
    for i in '1'..='9' {
        for j in '1'..i {
            ans = ans.max(
                s.split(|x| x != i && x != j)
                    .map(|x| x.len())
                    .max()
                    .unwrap_or_default(),
            );
        }
    }
    println!("{}", ans);
}
```

## Solution 2

Let's denote using $R_l$, the rightmost point of the longest continuous sequence of two or less types of fruits starting from $S_l$. That is, there are always two or less types of fruits in $S_l, S_{l+1}, \cdots, S_{R_l}$. Removing $S_l$ from the sequence, there are still two or less types of fruits in $S_{l+1}, \cdots, S_{R_l}$ so $R_{l+1}$ is always larger than or equal to $R_l$. Therefore, $R_l$ increases with $l.

Supposing $R_{l-1}$ was calculated, and since we know $R_l$ to be larger than or equal to $R_{l-1}$, we can use a naive solution using a loop from $r = R_{l-1}$ increasing $r$ by $1$ each iteration looking for the maximum $r$ such that there are two or less types of fruits in $S_{l}, \cdots, S_r$. Since $r$ increases by $N$ in the loop, the number of iterations does not exceed $O(N)$.

Now we just need to find the types of fruits in $S_l, \cdots, S_r$ fast. This can be done by maintaining a `cnt` array of length $10$ in which we store the count of each type of fruit in the current range $S_l, \cdots, S_r$,  and if we also store the number of types of fruits with more than $1$ fruit, this can be solved in $O(1)$ time. Total complexity is $O(N)$.

Variable `r` is used to maintain $R_l + 1$ in the below code.

### Code (C++)

```cpp
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N;
    cin >> N;
    vector<int> S(N);
    for (int &s : S)
        cin >> s;
    int ans = 0, r = 0, non_zero = 0;
    vector<int> cnt(10);
    for (int l = 0; l < N; l++)
    {
        while (r < N)
        {
            int nxt_non_zero = non_zero + (cnt[S[r]] == 0 ? 1 : 0);
            if (nxt_non_zero <= 2)
            {
                cnt[S[r]]++;
                r++;
                non_zero = nxt_non_zero;
            }
            else
                break;
        }
        ans = max(ans, r - l);
        cnt[S[l]]--;
        if (cnt[S[l]] == 0)
            non_zero--;
    }
    cout << ans << endl;
}
```

### Code (Python)

```python
def main():
    N = int(input())
    S = map(int, input().split())

    ans = r = non_zero = 0
    cnt = [0]*10

    for l in range(N):
        while r < N:
            nxt_non_zero = non_zero + (1 if cnt[S[r]] == 0 else 0)
            if nxt_non_zero <= 2:
                cnt[S[r]] += 1
                r += 1
                non_zero = nxt_non_zero
            else:
                break
        ans = max(ans, r - l)
        cnt[S[l]] -= 1
        if cnt[S[l]] == 0:
            non_zero -= 1

    print(ans)


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

### Code (Rust)

```rust
use std::io::*;

fn main() {
    let n = read_vec()[0];
    let s = read_vec();

    let mut ans = 0;
    let mut r = 0;
    let mut non_zero = 0;
    let mut cnt = [0; 10];

    for l in 0..n {
        while r < n {
            let nxt_non_zero = non_zero + if cnt[s[r] as usize] == 0 { 1 } else { 0 };
            if nxt_non_zero <= 2 {
                cnt[s[r]] += 1;
                r += 1;
                non_zero = nxt_non_zero;
            } else {
                break;
            }
        }
        ans = ans.max(r - l);
        cnt[s[l]] -= 1;
        if cnt[s[l]] == 0 {
            non_zero -= 1;
        }
    }

    println!("{}", ans);
}

fn read_vec() -> Vec<usize> {
    let mut s = String::new();
    stdin().read_line(&mut s).unwrap();
    s.split_whitespace().map(|x| x.parse().unwrap()).collect()
}
```



The largest number in the largest common subsequence of $A$ and $B$ is the largest number $x$ which appears in both $A$ and $B$. By the definition of lexicographical order, we need the first element to be as large as possible, so the first element of the largest common subsequence is $x$.

If $x$ appears multiple times, we use a greedy approach in which we use $x$ from the front of $A$ and $B$ first. Using $x$ which appears first in the sequences allows us to have a longer subsequence at the back, increasing the number of possible largest common subsequences.

In conclusion, we look for the first occurence of the largest element which appears in both $A$ and $B$, and repeatedly solve that same problem for the sequence which comes after that element. Total time complexity is roughly $O((N+M + \max A_i + \max B_i)^2)$.

As a side note, we can use data structures such as a priority queue in our implementation to optimize our time complexity to $O((N+M) \log (N+M))$.

### Code (C++20)

```cpp
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int N;
    cin >> N;
    vector<int> A(N);
    for (int &a : A)
        cin >> a;
    int M;
    cin >> M;
    vector<int> B(M);
    for (int &b : B)
        cin >> b;

    int mx = max(ranges::max(A), ranges::max(B));
    auto it_a = A.begin(), it_b = B.begin();
    vector<int> ans;

    for (int i = mx; i >= 1; --i)
    {
        while (true)
        {
            auto nxt_a = find(it_a, A.end(), i), nxt_b = find(it_b, B.end(), i);
            if (nxt_a == A.end() || nxt_b == B.end())
                break;

            ans.push_back(i);
            it_a = next(nxt_a), it_b = next(nxt_b);
        }
    }

    cout << ans.size() << endl;
    for (int v : ans)
        cout << v << " ";
    cout << endl;
    return 0;
}
```

### Code (Python)

```python
def main():
    input()
    a = list(map(int, input().split()))
    input()
    b = list(map(int, input().split()))

    mx = max(max(a), max(b))
    ans = []
    for i in range(mx, 0, -1):
        while True:
            if i not in a or i not in b:
                break

            ans.append(i)
            a = a[a.index(i)+1:]
            b = b[b.index(i)+1:]

    print(len(ans))
    print(*ans, sep=' ')


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

### Code (Rust)

```rust
use std::io::*;

fn main() {
    read_vec();
    let a = read_vec();
    read_vec();
    let b = read_vec();

    let mx = *a.iter().chain(b.iter()).max().unwrap();
    let mut a = &a[..];
    let mut b = &b[..];
    let mut ans = Vec::new();
    for i in (1..=mx).rev() {
        loop {
            let ai = a.iter().position(|&x| x == i);
            let bi = b.iter().position(|&x| x == i);
            if ai == None || bi == None {
                break;
            }
            ans.push(i);
            a = &a[ai.unwrap() + 1..];
            b = &b[bi.unwrap() + 1..];
        }
    }
    println!("{}", ans.len());
    for i in ans {
        print!("{} ", i);
    }
    println!();
}

fn read_vec() -> Vec<usize> {
    let mut s = String::new();
    stdin().read_line(&mut s).unwrap();
    s.trim()
        .split_whitespace()
        .into_iter()
        .map(|x| x.parse().unwrap())
        .collect()
}
```



## Solution

Finding the size of a set can be thought of as counting the number of elements in it. Thus, the given equation can be changed as follows.
$$
a_{k} = \sum_{\substack{\tau \subseteq \{1, \cdots, N\}\\|\tau|=k}}\sum_{s \in \mathcal{S}} \left[s \in \bigcap_{i \in \tau} S_{i}\right]_{\mathbf{1}}
$$

Here, $\mathcal{S}$ is the set of all elements which can be in the set, that is, $\mathcal{S} = \bigcup_{i} S_{i}$, and $[a \in A]_{\mathbf{1}}$ is a mathematical expression which evaluates to $1$ if $a$ is in set $A$, and $0$ if it isn't.

Now let's change the order of the sums and think of the expression **for each $s$** . For any $s$, if the intersection of $k$ sets is to include $s$, all $k$ sets must include $s$. If $c_{s}$ is the number of times $s$ is included in $S_{i}$, we need to choose $k$ sets from the $c_{s}$ sets which have $s$ as an element for all the chosen sets to include $s$. There are exactly $\binom{c_{s}}{k}$ cases of this.

We can summarize the above as follows.

$$
\begin{aligned}a_{k} &= \sum_{\substack{\tau \subseteq \{1, \cdots, N\}\\|\tau|=k}}\sum_{s \in \mathcal{S}} \left[s \in \bigcap_{i \in \tau} S_{i}\right]_{\mathbf{1}} \\&= \sum_{s \in \mathcal{S}} \sum_{\substack{\tau \subseteq \{1, \cdots, N\}\\|\tau|=k}}\left[s \in \bigcap_{i \in \tau} S_{i}\right]_{\mathbf{1}}\\&= \sum_{s \in \mathcal{S}}\binom{c_{s}}{k}.\end{aligned}
$$

The time taken for finding the binomial coefficient can be reduced to $\mathcal{O}(1)$. In $\binom{a}{b} = \frac{a!}{b!(a-b)!}$, $a$ and $b$ cannot exceed $10^{6}$. Therefore, if we precompute all the factorials and their modular inverse modulo $p = 998\,244\,353$ $0!$, $1!$, $2!$, $\cdots$, $10^{6}!$, $(0!)^{-1}$, $(1!)^{-1}$, $(2!)^{-1}$, $\cdots$, $(10^{6}!)^{-1}$, we can find the binomial coefficient very quickly by just two multiplications under modulo $p$.

However in this problem, $|S|$ does not exceed $N$, and since we need the values for all $k = 1, \cdots, N$, this method still takes $\mathcal{O}(N^{2})$ resulting in a TLE verdict.

To further reduce the time taken, we need to focus on the fact that if $c_{s} < k$, $\binom{c_{s}}{k} = 0$. Since the important factor is the number of appearances of $s$, we find $a_{k}$ by incrementing $k$ starting from $k = 1$ with $c_{s}$ computed in prior so that we ignore $s$ the moment $c_{s} < k$ is satisfied. This allows us to find all $a_{k}$ in time proportional to $\sum_{s \in \mathcal{S}} c_{s} + \mathcal{O}(N)$.

However, since $\sum_{s \in \mathcal{S}} c_{s} = a_{1}$ in the above expression, and $a_{1}$ is the sum of the sizes of individual sets, this value is $\sum_{i} \left|S_{i}\right|$ which according to the problem statement does not exceed $10^{6}$! Using this optimization, we can write code which takes a total of $\mathcal{O}(N)$ time (excluding the time taken for sorting).

### Code (C++20)

```cpp
#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
using namespace std;

const int MOD = 998'244'353;
int ipow(int a, int b)
{
    if (b == 0)
        return 1;
    if (b % 2 == 1)
        return 1LL * a * ipow(a, b - 1) % MOD;
    long long r = ipow(a, b / 2);
    return r * r % MOD;
}
int modinv(int v) { return ipow(v, MOD - 2); }
struct Comb
{
    vector<int> fact, rfact;
    Comb(int sz) : fact(sz + 1), rfact(sz + 1)
    {
        fact[0] = 1;
        for (int i = 1; i <= sz; i++)
            fact[i] = 1LL * i * fact[i - 1] % MOD;
        rfact[sz] = modinv(fact[sz]);
        for (int i = sz - 1; i >= 0; --i)
            rfact[i] = 1LL * (i + 1) * rfact[i + 1] % MOD;
        assert(rfact[0] == 1);
    }
    int C(int n, int k)
    {
        return 1LL * fact[n] * rfact[k] % MOD * rfact[n - k] % MOD;
    }
};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin >> N;
    vector<int> arr, coeff(N + 1);
    for (int i = 0; i < N; i++)
    {
        int t;
        cin >> t;
        while (t--)
        {
            int x;
            cin >> x;
            arr.push_back(x);
        }
    }
    ranges::sort(arr);
    int last = -1, cnt = 0;
    for (int x : arr)
    {
        if (last != x)
        {
            if (cnt > 0)
                ++coeff[cnt];
            last = x, cnt = 0;
        }
        ++cnt;
    }
    ++coeff[cnt];

    Comb comb(1'000'000);

    vector<int> result(N + 1);
    for (int i = 0; i <= N; i++)
        if (coeff[i])
            for (int j = 0; j <= i; j++)
                result[j] = (result[j] + 1LL * coeff[i] * comb.C(i, j)) % MOD;

    for (int i = 1; i <= N; i++)
        cout << result[i] << '\n';
}
```

### Code (Python)

```python
import sys


def input(): return sys.stdin.readline().rstrip()


MOD = 998_244_353


class Comb:
    def __init__(self, sz):
        self.fact = [1] * (sz + 1)
        self.rfact = [1] * (sz + 1)
        for i in range(1, sz + 1):
            self.fact[i] = (i * self.fact[i - 1]) % MOD
        self.rfact[sz] = pow(self.fact[sz], -1, MOD)
        for i in range(sz - 1, -1, -1):
            self.rfact[i] = ((i + 1) * self.rfact[i + 1]) % MOD
        assert self.rfact[0] == 1

    def C(self, n, k):
        return (self.fact[n] * self.rfact[k] % MOD * self.rfact[n - k]) % MOD


def main():
    N = int(input())
    arr = []
    coeff = [0] * (N + 1)
    for _ in range(N):
        arr.extend(list(map(int, input().split()))[1:])
    arr.sort()

    cnt, last = 0, -1
    for x in arr:
        if last != x:
            if cnt > 0:
                coeff[cnt] += 1
            last, cnt = x, 0
        cnt += 1
    coeff[cnt] += 1

    comb = Comb(1_000_000)

    result = [0] * (N + 1)
    for i in range(N + 1):
        if coeff[i]:
            for j in range(i + 1):
                result[j] = (result[j] + coeff[i] * comb.C(i, j)) % MOD

    for i in range(1, N + 1):
        print(result[i])


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

### Code (Rust)

```rust
use std::{cell::*, collections::HashMap, fmt::Debug, io::*, str::*};

const MOD: u64 = 998_244_353;
fn ipow(a: u32, b: u32) -> u32 {
    (match b {
        0 => 1,
        v if v % 2 == 0 => {
            let c: u64 = ipow(a, v / 2) as u64;
            c * c % MOD
        }
        v if v % 2 == 1 => a as u64 * ipow(a, b - 1) as u64 % MOD,
        _ => panic!(),
    }) as u32
}
fn modinv(a: u32) -> u32 {
    ipow(a, MOD as u32 - 2)
}
struct Comb {
    fact: Vec<u32>,
    rfact: Vec<u32>,
}
impl Comb {
    fn new(sz: usize) -> Comb {
        let mut fact = vec![1; sz + 1];
        let mut rfact = vec![1; sz + 1];
        fact[0] = 1;
        for i in 1..=sz {
            fact[i] = ((i as u64) * (fact[i - 1] as u64) % MOD) as u32;
        }
        rfact[sz] = modinv(fact[sz]);
        for i in (0..sz).rev() {
            rfact[i] = (((i + 1) as u64) * (rfact[i + 1] as u64) % MOD) as u32;
        }
        assert_eq!(rfact[0], 1);
        Comb { fact, rfact }
    }
    fn c(&self, n: usize, k: usize) -> u32 {
        ((self.fact[n] as u64) * (self.rfact[k] as u64) % MOD * (self.rfact[n - k] as u64) % MOD)
            as u32
    }
}

fn main() {
    let n = read_vec()[0];
    let mut hm = HashMap::new();
    for _ in 0..n {
        for v in read_vec::<u32>().into_iter().skip(1) {
            hm.insert(v, *hm.get(&v).unwrap_or(&0) + 1);
        }
    }
    let comb = Comb::new(1_000_000);
    let mut ans = vec![0; n + 1];
    for v in hm.values().cloned() {
        for i in 1..=v {
            ans[i] = (ans[i] + comb.c(v, i)) % (MOD as u32);
        }
    }

    for i in ans.into_iter().skip(1) {
        println!("{} ", i);
    }
}

thread_local! {
    static STDIN: RefCell<StdinLock<'static>> = RefCell::new(stdin().lock());
    static STDOUT: RefCell<BufWriter<StdoutLock<'static>>> = RefCell::new(BufWriter::new(stdout().lock()));
}
fn read_vec<T: FromStr>() -> Vec<T>
where
    <T as FromStr>::Err: Debug,
{
    let mut s = String::new();
    STDIN.with(|cell| {
        cell.borrow_mut().read_line(&mut s).unwrap();
    });
    s.split_whitespace().map(|x| x.parse().unwrap()).collect()
}
#[macro_export]
macro_rules! println {
    ($($t:tt)*) => {
        STDOUT.with(|cell| writeln!(cell.borrow_mut(), $($t)*).unwrap());
    };
}
```

## Solution

Let's denote the cost of the MST of $G$ as $\mathrm{mst}(G)$.

For an arbitrary graph $G$, increasing the weight of one of its edges by $1$ increases $\mathrm{mst}(G)$ by a maximum of $1$. This is because where $G'$ is the graph with the increased weight, the cost of the tree corresponding to the MST of $G$ increases by a maximum of $1$, and $\mathrm{mst}(G')$ is smaller than or equal to this value.

Now let's consider the following procedure. We increase the weight of the $i$-th edge by $1$ starting from $l_i$ until it becomes $r_i$. We repeat this process in order starting from the $1$-st edge to the $M$-th edge.

Where $t$ is the weight we have increased in total, we will call this graph  $G_t$, and we will denote the sum of $r_i - l_i$ as $X$. Throughout the above procedure, $\mathrm{mst}(G_t)$ monotonically increases across all integers between $\mathrm{mst}(G_0)$ and $\mathrm{mst}(G_X)$ inclusive.

Therefore, if $\mathrm{mst}(G_0) \le K \le \mathrm{mst}(G_X)$, we can find the point where $\mathrm{mst}(G_t) = K$ is first satisfied by running a binary search on values of $t$. $G_t$ can be constructed in $O(M)$ time, and the cost of the MST can be calculated in $O(M\log M)$ time, resulting in a total time complexity of $O(M \log M \log X)$ which is sufficient to solve this problem.

### Code (C++)

```cpp
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;

struct DisjointSet
{
    vector<int> par;

    DisjointSet(int N) : par(N)
    {
        iota(par.begin(), par.end(), 0);
    }

    int find(int x)
    {
        if (par[x] == x)
            return x;
        return par[x] = find(par[x]);
    }

    bool merge(int x, int y)
    {
        x = find(x), y = find(y);
        if (x == y)
            return false;
        par[y] = x;
        return true;
    }
};

struct Edge
{
    int u, v;
    long long c;
    bool operator<(const Edge &E) const { return c < E.c; }
};

long long mst(int N, const vector<tuple<int, int, long long, long long>> &G, long long t)
{
    // construct G_t
    vector<Edge> E;
    for (auto [u, v, l, r] : G)
    {
        long long c = min(t, r - l);
        E.push_back({u, v, l + c});
        t -= c;
    }
    sort(E.begin(), E.end());

    // find MST
    DisjointSet dsu(N + 1);
    long long sum = 0;
    for (auto [x, y, c] : E)
        if (dsu.merge(x, y))
            sum += c;
    return sum;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N, M;
    long long K;
    cin >> N >> M >> K;

    vector<tuple<int, int, long long, long long>> G(M);
    long long X = 0;
    for (auto &[u, v, l, r] : G)
    {
        cin >> u >> v >> l >> r;
        X += r - l;
    }

    // binary search
    long long s = -1, e = X;
    while (s + 1 < e)
    {
        long long m = (s + e) / 2;
        if (mst(N, G, m) >= K)
            e = m;
        else
            s = m;
    }

    // print answer
    if (mst(N, G, e) == K)
    {
        cout << "YES\n";
        for (auto &[u, v, l, r] : G)
        {
            int c = min(e, r - l);
            cout << min(l + c, r) << '\n';
            e -= c;
        }
    }
    else
    {
        cout << "NO\n";
    }

    return 0;
}
```

### Code (Python)

```python
import sys

def input():
    return sys.stdin.readline().rstrip()

class DisjointSet:
    def __init__(self, N):
        self.par = [i for i in range(N + 1)]

    def find(self, x):
        if self.par[x] == x:
            return x
        self.par[x] = self.find(self.par[x])
        return self.par[x]

    def merge(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return False
        self.par[y] = x
        return True

def mst(N, G, t):
    # construct G_t
    E = []
    for u, v, l, r in G:
        c = min(t, r - l)
        E.append((u, v, l + c))
        t -= c
    E.sort(key=lambda x: x[2])

    # find MST
    dsu = DisjointSet(N)
    sum = 0
    for x, y, c in E:
        if dsu.merge(x, y):
            sum += c
    return sum

def main():
    N, M, K = [int(x) for x in input().split()]
    G = []
    for i in range(M):
        u, v, l, r = [int(x) for x in input().split()]
        G.append((u, v, l, r))

    X = sum(r - l for u, v, l, r in G)

    # binary search
    s, e = -1, X
    while s + 1 < e:
        m = (s + e) // 2
        if mst(N, G, m) >= K:
            e = m
        else:
            s = m

    # print answer
    if mst(N, G, e) == K:
        print("YES")
        for u, v, l, r in G:
            c = min(e, r - l)
            print(min(l + c, r))
            e -= c
    else:
        print("NO")

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

### Code (Rust)

```rust
use std::{cell::*, fmt::Debug, io::*, str::*};

struct DisjointSet {
    par: Vec<usize>,
}

impl DisjointSet {
    fn new(n: usize) -> DisjointSet {
        DisjointSet {
            par: (0..n).collect(),
        }
    }

    fn find(&mut self, x: usize) -> usize {
        if self.par[x] == x {
            x
        } else {
            let parent = self.find(self.par[x]);
            self.par[x] = parent;
            parent
        }
    }

    fn merge(&mut self, x: usize, y: usize) -> bool {
        let x = self.find(x);
        let y = self.find(y);
        if x == y {
            false
        } else {
            self.par[y] = x;
            true
        }
    }
}

struct Edge {
    u: usize,
    v: usize,
    c: i64,
}

fn mst(n: usize, g: &Vec<(usize, usize, i64, i64)>, mut t: i64) -> i64 {
    // construct G_t
    let mut e = Vec::new();
    for &(u, v, l, r) in g {
        let c = t.min(r - l);
        e.push(Edge { u, v, c: l + c });
        t -= c;
    }
    e.sort_by_key(|k| k.c);

    // find MST
    let mut dsu = DisjointSet::new(n + 1);
    let mut sum = 0;
    for edge in e {
        if dsu.merge(edge.u, edge.v) {
            sum += edge.c;
        }
    }
    sum
}

fn main() {
    let (n, m, k) = {
        let v = read_vec();
        (v[0], v[1], v[2] as i64)
    };

    let mut g = vec![(0, 0, 0, 0); m];
    for (u, v, l, r) in &mut g {
        let edge = read_vec();
        *u = edge[0];
        *v = edge[1];
        *l = edge[2] as i64;
        *r = edge[3] as i64;
    }
    let x = g.iter().map(|&(_u, _v, l, r)| r - l).sum();

    // binary search
    let mut s = -1;
    let mut e = x;
    while s + 1 < e {
        let m = (s + e) / 2;
        if mst(n, &g, m) >= k {
            e = m;
        } else {
            s = m;
        }
    }

    // print answer
    if mst(n, &g, e) == k {
        println!("YES");
        let mut e = e;
        for (_u, _v, l, r) in g {
            let c = e.min(r - l);
            println!("{}", r.min(l + c));
            e -= c;
        }
    } else {
        println!("NO");
    }
}

thread_local! {
    static STDIN: RefCell<StdinLock<'static>> = RefCell::new(stdin().lock());
    static STDOUT: RefCell<BufWriter<StdoutLock<'static>>> = RefCell::new(BufWriter::new(stdout().lock()));
}
fn read_vec<T: FromStr>() -> Vec<T>
where
    <T as FromStr>::Err: Debug,
{
    let mut s = String::new();
    STDIN.with(|cell| {
        cell.borrow_mut().read_line(&mut s).unwrap();
    });
    s.split_whitespace().map(|x| x.parse().unwrap()).collect()
}
#[macro_export]
macro_rules! println {
    ($($t:tt)*) => {
        STDOUT.with(|cell| writeln!(cell.borrow_mut(), $($t)*).unwrap());
    };
}
```



## Solution

Let's think of the buildings visited in reverse order of visit. This changes the operation of visiting $u \rightarrow v$ then re-coloring $v$ in color $p$ to that of coloring $v$ in color $p$ when visiting $v \rightarrow u$. However, if $v$ is already colored, nothing is done.

Thus, the problem is about finding an order of visit such that all buildings are visited with the additional condition that an edge of color $r_v$ must be used when visiting the building for the first time. Any edge can be used second time onwards.

Using this, we run a DFS such that each building is visited twice.

- If building $v$ is visited for the first time, use an edge of color $r_v$ to move from one building to another.
- If building $v$ is visited for the second time, visit adjacent buildings which were not yet visited twice.

Finally, print the answer in reverse order.

If there is no adjacent edge of color $r_v$ or all the buildings are not connected, the answer is `NO`. Otherwise, the above algorithm works properly so the answer is always  `YES`. Since each building is visited a maximum of two times (ignoring the return call of the dfs function), the total number of visits is less than or equal to $4N$.

### Code (C++)

```cpp
#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>
using namespace std;

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

    int N, M, K;
    cin >> N >> M >> K;
    vector<int> R(N);
    for (int &r : R)
        cin >> r;
    vector<vector<pair<int, int>>> G(N);
    for (int i = 0; i < M; i++)
    {
        int u, v, c;
        cin >> u >> v >> c;
        --u, --v;
        G[u].emplace_back(v, c);
        G[v].emplace_back(u, c);
    }
    vector<int> vis(N), history;
    function<bool(int)> dfs = [&](int u)
    {
        ++vis[u];
        history.push_back(u);
        if (vis[u] == 1)
        {
            // only can jump to matching color
            for (auto [v, c] : G[u])
                if (R[u] == c)
                {
                    if (vis[v] != 2)
                    {
                        bool ret = dfs(v);
                        history.push_back(u);
                        return ret;
                    }
                    else
                    {
                        history.push_back(v);
                        return dfs(u);
                    }
                }
            return false;
        }
        else
        {
            // visit everywhere
            for (auto [v, c] : G[u])
                if (vis[v] != 2)
                {
                    if (!dfs(v))
                        return false;
                    history.push_back(u);
                }
            return true;
        }
    };

    bool res = dfs(0);
    if (!res || ranges::any_of(vis, [](int x)
                               { return x != 2; }))
    {
        cout << "NO\n";
    }
    else
    {
        cout << "YES\n";
        cout << history.size() << '\n';
        ranges::reverse(history);
        for (int h : history)
            cout << h + 1 << ' ';
        cout << '\n';
    }

    return 0;
}
```

### Code (Python)

```python
import sys
sys.setrecursionlimit(1_000_000)


def input(): return sys.stdin.readline().rstrip()


def main():

    n, m, _ = map(int, input().split())
    g = [[] for _ in range(n)]
    r = list(map(int, input().split()))
    for _ in range(m):
        u, v, c = map(int, input().split())
        u -= 1
        v -= 1
        g[u].append((v, c))
        g[v].append((u, c))

    vis = [0] * n
    history = []

    def dfs(u):
        vis[u] += 1
        history.append(u)
        if vis[u] == 1:
            # only can jump to matching color
            for v, c in g[u]:
                if r[u] == c:
                    if vis[v] != 2:
                        ret = dfs(v)
                        history.append(u)
                        return ret
                    else:
                        # visit v, and return u.
                        history.append(v)
                        return dfs(u)
            return False
        else:
            # visit everywhere
            for v, _ in g[u]:
                if vis[v] != 2:
                    if not dfs(v):
                        return False
                    history.append(u)
            return True

    res = dfs(0)
    if not res or any(x != 2 for x in vis):
        print('NO')
    else:
        print('YES')
        print(len(history))
        print(' '.join(map(lambda x: str(x+1), history[::-1])))


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

### Code (Rust)

```rust
use std::{cell::*, fmt::Debug, io::*, str::*};

fn main() {
    let (n, m, _) = {
        let v = read_vec();
        (v[0], v[1], v[2])
    };
    let mut g = vec![Vec::new(); n];
    let r = read_vec();
    for _ in 0..m {
        let (u, v, c) = {
            let v = read_vec::<usize>();
            (v[0] - 1, v[1] - 1, v[2])
        };
        g[u].push((v, c));
        g[v].push((u, c));
    }

    struct Dfs<'a> {
        g: &'a Vec<Vec<(usize, usize)>>,
        r: &'a Vec<usize>,
        vis: Vec<usize>,
        history: Vec<usize>,
    }
    impl Dfs<'_> {
        fn dfs(&mut self, u: usize) -> bool {
            self.vis[u] += 1;
            self.history.push(u);
            match self.vis[u] {
                1 => {
                    // only can jump to matching color
                    for &(v, c) in &self.g[u] {
                        if self.r[u] == c {
                            if self.vis[v] != 2 {
                                let ret = self.dfs(v);
                                self.history.push(u);
                                return ret;
                            } else {
                                // visit v, and return u.
                                self.history.push(v);
                                return self.dfs(u);
                            }
                        }
                    }
                    false
                }
                2 => {
                    // visit everywhere
                    for &(v, _) in &self.g[u] {
                        if self.vis[v] != 2 {
                            if !self.dfs(v) {
                                return false;
                            }
                            self.history.push(u);
                        }
                    }
                    true
                }
                _ => panic!(),
            }
        }
    }

    let mut dfs = Dfs {
        g: &g,
        r: &r,
        vis: vec![0; n],
        history: Vec::new(),
    };
    let res = dfs.dfs(0);
    if !res || dfs.vis.iter().any(|&x| x != 2) {
        println!("NO");
    } else {
        println!("YES");
        println!("{}", dfs.history.len());
        for i in dfs.history.into_iter().rev() {
            print!("{} ", i + 1);
        }
        println!();
    }
}

thread_local! {
    static STDIN: RefCell<StdinLock<'static>> = RefCell::new(stdin().lock());
    static STDOUT: RefCell<BufWriter<StdoutLock<'static>>> = RefCell::new(BufWriter::new(stdout().lock()));
}
fn read_vec<T: FromStr>() -> Vec<T>
where
    <T as FromStr>::Err: Debug,
{
    let mut s = String::new();
    STDIN.with(|cell| {
        cell.borrow_mut().read_line(&mut s).unwrap();
    });
    s.split_whitespace().map(|x| x.parse().unwrap()).collect()
}
#[macro_export]
macro_rules! println {
    ($($t:tt)*) => {
        STDOUT.with(|cell| writeln!(cell.borrow_mut(), $($t)*).unwrap());
    };
}
#[macro_export]
macro_rules! print {
    ($($t:tt)*) => {
        STDOUT.with(|cell| write!(cell.borrow_mut(), $($t)*).unwrap());
    };
}
```

