First, since all sequences of choices have same probability to occur, we can turn it into a counting problem and divide the answer by the number of possibility, that is

where $$$ope_m$$$ represent the sequence of operation done to the array $$$b_n$$$($$$ope_i \in [1, n] \text{ }\forall i$$$).

At first glance, the problem seems to have too much stuff going on, so let's try to solve a more constrained version(invent subtasks) and see if we can generalize the solution back to the original problem later.

Subtask: $$$v = 1, a_i = 0 \text{ }\forall i \in [1, n]$$$, operations are point add rather than suffix add

Since constraints on $$$a_n$$$ and $$$v$$$ feel like a "noise" and not related to the core of the problem, also doing suffix add feels a bit annoying, let's get rid of them first. How can we solve this problem?

Assume we label element added at the $$$i$$$-th operation with $$$i$$$, then by the product trick, we can think of $$$\prod_\limits{i = 1}^n b_i$$$ as counting the number of ways to pick one element from each entry of sequence $$$b_n$$$, then we can further enumerate all possible choices of elements, that is

where $$$c_i$$$ represents the label of element chosen in $$$i$$$-th entry, and we only need to consider sequences satisfy $$$c_i \in [1, m] \text{ }\forall i, c_i \neq c_j \forall i \neq j$$$

Then using contribution to the sum trick (or swapping sigma/double counting...), we get

Which boils down to a simple combinatoric problem, for a fixed $$$c_n$$$, we can freely distribute elements not in $$$c_n$$$, and there are $$$\frac{m!}{(m-n)!}$$$ possible $$$c_n$$$ we need to consider, thus the answer will be

Now, let's lift the constraints one by one, trying to generalize the solution back to the original problem.

Subtask: $$$v = 1, a_i = 0 \text{ }\forall i \in [1, n]$$$

I decide to lift the suffix add constraint first because it feels more related to the core of the problem. How is this modification change our solution?

Since adding suffix $$$[i, n]$$$ should be equivalent to adding elements of same label to all entries in $$$[i, n]$$$, the condition $$$[\text{element }c_i\text{ belongs to i-th entry }\forall i]$$$ should be equivalent to $$$[ope_{c_i} \leq i \text{ }\forall i]$$$ rather than the above one, and it is possible to pick element of same label from different entries, thus condition for $$$c_n$$$ become just $$$c_i \in [1, m]$$$, so we can no longer assume the number of free elements is $$$m - n$$$. Which give us

Now the stuffs start to get complicated and can't be dealt with a simple formula, so instead of deriving a formula, let try to use the following DP to handle this.

About the transition, since we can let $$$c_{i + 1}$$$ be either an already appeared element or a new one, and if it is a new one, we should also determine the choice of respective operation, which have $$$(i + 1)$$$ possibility by the new condition we just stated above, so the transitions should be

and we consider the choices of free elements and permute elements in $$$c_n$$$ by multiplying some factor afterward, which gives us the answer

the original problem

Finally, let try to deal with constraint on $$$v$$$ and $$$a_n$$$, for $$$v$$$, the only change is that there are $$$v$$$ elements of same label added to a single entry rather then one element, thus we can choose $$$1$$$ elements out of $$$v$$$ elements from every entry. And for $$$a_n$$$, we can just let there be some extra elements before we do the operation, and when consider $$$i$$$-th slot, except choosing an element come from the operations, we can also choose the one already in the entry before the operations, which gives us the following transitions

and the final answer will be

After the long long thinking on the problem, all we need to do is to write a few line of code, which is amazing!

Conclusion

When solving this problem, I feel myself using a lot of techniques and problem solving skill I've ever learnt in my entire CP journey, and even I've known these stuffs for a fairly long time, I still got fascinated by the solution itself, especially the process of clarifying the core of the problem model by inventing proper subtasks, and the powerfulness of turning a counting problem into formula, which can lead further to the usage of some common techniques (product trick, contribution to the sum, DP, etc...)

Though I feel the whole solving path is a bit too long for me to solve it during contest, so if you have any shorter/smarter way to come up with the solution, please let me know by commenting below, I would be appreciated.

And finally, thanks for your reading and I hope this blog gives you some insights of problem solving :)

According to Cayley-Hamilton theorem, the power of a $$$n$$$ times $$$n$$$ matrix can be seen as a linear recurrence have atmost $$$n$$$ terms, so let say we have some $$$dp[n][m]$$$ which every $$$dp[i]$$$ is a $$$n$$$ times $$$1$$$ vector, and we can get $$$dp[i]$$$ from the previous $$$dp[j] (j < i)$$$ by multiplying a transition matrix $$$A_{n \times n}$$$, then we can manipulate Cayley-Hamilton theorem like below to get a linear recurrence of a certain entries of $$$dp[i]$$$, then brute-force the first $$$2n$$$ terms of $$$dp[i] (i \leq 2n)$$$, plug all of them into Berlekamp-Massey, and we will get the actual recurrence relation of a certain entries of $$$dp[i]$$$, finally compute the k-th term of linear recurrence in $$$O(n^2lgk)$$$ or $$$O(nlgnlgk)$$$ using FFT.

($$$A$$$ is a $$$n$$$ times $$$n$$$ matrix, $$$b_i$$$ is a $$$n$$$ times $$$1$$$ vector whose entry are all $$$0$$$ except i-th row is $$$1$$$)

Assume we will construct a palidrome $$$S$$$ of length $$$n + |s|$$$, then we can just build the left half of the string then the rest will be fixed.

To make sure $$$S$$$ contain $$$s$$$ as a subsequence, we can maintain two position $$$L, R$$$ which means $$$s[i](L \le i \le R)$$$ have not been inserted to string $$$S$$$, when we add a letter $$$X$$$ at the end of $$$S$$$, if $$$X = s[L]$$$, then we let $$$L$$$ become $$$L + 1$$$(because we already add $$$s[L]$$$ to $$$S$$$, if $$$X = s[R]$$$, then we let $$$R$$$ become $$$R - 1$$$.

So we can get the following dp solution.

$$$dp[i][L][R]$$$ store the number of string have length $$$i$$$, and $$$s[j](L \le j \le R)$$$ have not been inserted to the string. then we will have the following transition.

\begin{equation} dp[i][L][R] \mathrel{+}= \begin{cases} dp[i-1][L][R] & \text{if } L = R + 1 \text{ or } (s[L] \neq j \text{ and } s[R] \neq j)\\ dp[i-1][L-1][R] & \text{if } s[L-1] = j \text{ and } (s[R] \neq j \text{ or } L = R + 1)\\ dp[i-1][L][R + 1] & \text{if } s[R + 1] = j \text{ and } (s[L] \neq j \text{ or } L = R + 1)\\ dp[i-1][L-1][R + 1] & \text{if } s[L-1] = s[R + 1] = j \end{cases}
\end{equation}

time complexity: $$$O(26(n + |s|)|s|^2)$$$

#include<bits/stdc++.h>
//#define x() real()
//#define y() imag()
//#define int long long
//#define double long double
 
using namespace std;
 
using pii = pair<int, int>;
using pll = pair<long long, long long>;
//using Point = complex<double>;
//using Vector = complex<double>;
//using Segment = pair<Point, Point>;

/*
enum {
  NO_SOL,
  MULTI_SOL,
  ONE_SOL
};
*/
vector<pii> ans;
map<int, int> Plus, Minus;
int check(pii xBound, pii yBound) {
  if (Plus.size() > 1 or Minus.size() > 1) {
    return 0;
  }

  int pfir, mfir;
  if (Plus.size() == 1) {
    for(pii X : Plus)
      pfir = X.first;
  }
  if (Minus.size() == 1) {
    for(pii X : Minus)
      mfir = X.first;
  }

  if (Plus.size() == 1 and Minus.size() == 1) {
    int x = (pfir + mfir) / 2;
    int y = (pfir &mdash; mfir) / 2;
    if (x + y != pfir or x &mdash; y != mfir)
      return 0;

    if (xBound.first <= x and x < xBound.second and
        yBound.first <= y and y < yBound.second) {
      ans.emplace_back(make_pair(x, y));
      return 2;
    } else
      return 0;
  } else if (Plus.size() == 1) {
    int D1 = xBound.first + yBound.first;
    int D2 = (xBound.second &mdash; 1) + (yBound.second &mdash; 1);

    if (pfir == D1) {
      ans.emplace_back(make_pair(xBound.first, yBound.first));
      return 2;
    } else if (pfir == D2) {
      ans.emplace_back(make_pair(xBound.second - 1, yBound.second - 1));
      return 2;
    } else if (D1 < pfir and pfir < D2)
      return 1;
    else
      return 0;
  } else if (Minus.size() == 1) {
    int D1 = xBound.first &mdash; (yBound.second &mdash; 1);
    int D2 = (xBound.second &mdash; 1) &mdash; yBound.first;

    if (mfir == D1) {
      ans.emplace_back(make_pair(xBound.first, yBound.second - 1));
      return 2;
    } else if (mfir == D2) {
      ans.emplace_back(make_pair(xBound.second - 1, yBound.first));
      return 2;
    } else if (D1 < mfir and mfir < D2)
      return 1;
    else
      return 0;
  }

  return 3;
}

signed main() {
  ios::sync_with_stdio(false), cin.tie(NULL);

  int N; cin >> N;
  /*
  vector<vector<int> > vec(N, vector<int>(3));
  for(int i = 0; i < N; i++) {
    cin >> vec[i][0] >> vec[i][1] >> vec[i][2];
  }
  sort(vec.begin(), vec.end(), [](vector<int> a, vector<int> b) {
    if (a[1] == b[1])
      return a[0] == b[0] ? a[2] < b[2] : a[0] < b[0];
    else
      return a[1] < b[1];
  });
  */
  vector<pair<pii, int> > whyJudgeFail(N);
  for(int i = 0; i < N; i++)
    cin >> whyJudgeFail[i].first.second >> whyJudgeFail[i].first.first >>
           whyJudgeFail[i].second;
  sort(whyJudgeFail.begin(), whyJudgeFail.end());
  vector<vector<int> > vec(N, vector<int>(3, 0));
  for(int i = 0; i < N; i++) {
    vec[i][0] = whyJudgeFail[i].first.second;
    vec[i][1] = whyJudgeFail[i].first.first;
    vec[i][2] = whyJudgeFail[i].second;
  }

  vector<int> Xcor, Ycor;
  for(int i = 0; i < N; i++) {
    Xcor.emplace_back(vec[i][0]);
    Ycor.emplace_back(vec[i][1]);
  }
  Xcor.emplace_back(-1e7);
  Ycor.emplace_back(-1e7);
  Xcor.emplace_back(1e7);
  Ycor.emplace_back(1e7);
  sort(Xcor.begin(), Xcor.end());
  sort(Ycor.begin(), Ycor.end());
  N += 2;

  bool infSol = false;
  for(int i = 0; i < N &mdash; 1; i++) {
    Plus.clear();
    Minus.clear();
    pii xRange = make_pair(Xcor[i], Xcor[i + 1]); //[L, R)
    if (xRange.first == xRange.second)
      continue;
    for(vector<int> &VEC : vec) {
      if (VEC[0] <= xRange.first) {
        if (Minus.find(Minus[VEC[0] &mdash; VEC[1] + VEC[2]]) == Minus.end())
          Minus[VEC[0] &mdash; VEC[1] + VEC[2]] = 1;
        else
          Minus[VEC[0] &mdash; VEC[1] + VEC[2]] += 1;
      } else {
        if (Plus.find(VEC[0] + VEC[1] &mdash; VEC[2]) == Plus.end())
          Plus[VEC[0] + VEC[1] &mdash; VEC[2]] = 1;
        else
          Plus[VEC[0] + VEC[1] &mdash; VEC[2]] += 1;
      }
    }   

    int tmp = check(xRange, make_pair(Ycor[0], Ycor[1]));
    if (tmp == 1) 
      infSol = true;

    int idx = 0;
    for(int j = 1; j < N - 1; j++) {
      pii yRange = make_pair(Ycor[j], Ycor[j + 1]);
      if (yRange.first == yRange.second)
        continue;

      while(idx < vec.size() and vec[idx][1] <= Ycor[j]) {
        if (vec[idx][0] <= xRange.first) {
          int origin = vec[idx][0] - vec[idx][1] + vec[idx][2];
          if (--Minus[origin] == 0) 
            Minus.erase(origin);
          if (Plus.find(vec[idx][0] + vec[idx][1] + vec[idx][2]) == Plus.end())
            Plus[vec[idx][0] + vec[idx][1] + vec[idx][2]] = 1;
          else
            Plus[vec[idx][0] + vec[idx][1] + vec[idx][2]] += 1;
        } else {
          int origin = vec[idx][0] + vec[idx][1] - vec[idx][2];
          if (--Plus[origin] == 0)
            Plus.erase(origin);
          if (Minus.find(vec[idx][0] - vec[idx][1] - vec[idx][2]) == Minus.end())
            Minus[vec[idx][0] - vec[idx][1] - vec[idx][2]] = 1;
          else
            Minus[vec[idx][0] - vec[idx][1] - vec[idx][2]] += 1;
        }
        idx++;
      } 

      int tmp = check(xRange, yRange);
      if (tmp == 1)
        infSol = true;
    }
  }

  sort(ans.begin(), ans.end());
  ans.resize(unique(ans.begin(), ans.end()) &mdash; ans.begin());

  if (infSol or ans.size() > 1)
    cout << "uncertain\n";
  else if (ans.size() == 1) 
    cout << ans[0].first << ' ' << ans[0].second << '\n';
  else
    cout << "impossible\n";

  return 0;
}