solved.ac Grand Arena #1

# Matching Socks

## Solution 1

If there's a number written odd number of times, it's impossible to pair that number entirely, inevitably leaving one left.

### Code (C++)

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

int main()
{
    vector<int> cnt(10);
    for (int i = 0; i < 5; i++)
    {
        int Ai;
        cin >> Ai;
        cnt[Ai]++;
    }
    for (int i = 0; i < 10; i++)
        if (cnt[i] % 2 == 1)
            cout << i << endl;
}
```

### Code (Python)

```python
def main():
    cnt = [0] * 10
    for i in range(5):
        Ai = int(input())
        cnt[Ai] += 1

    for i in range(10):
        if cnt[i] % 2 == 1:
            print(i)


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

## Solution 2

The properties of the [XOR (exclusive OR)](https://en.wikipedia.org/wiki/Exclusive_or#Bitwise_operation) operation $\oplus$ are as follows:

- Commutative law: $a \oplus b = b \oplus a$
- Associative law: $a \oplus (b \oplus c) = (a \oplus b) \oplus c$
- Identity element: $a \oplus 0 = a$
- Each element is its own inverse: $a \oplus a = 0$

Due to the properties of XOR, if you XOR the same number twice, the number will disappear. Thus, to find the only number that can't be paired, XOR all the numbers given in the input.

### Code (C++)

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

int main()
{
    int ans = 0;
    for (int i = 0; i < 5; i++)
    {
        int Ai;
        cin >> Ai;
        ans ^= Ai;
    }
    cout << ans << endl;
}
```

### Code (Python)

```python
def main():
    ans = 0
    for i in range(5):
        Ai = int(input())
        ans ^= Ai

    print(ans)


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



# Shiritori

## Solution 1

Replace `?` with each $A_1, \cdots, A_M$, and verify whether it's a valid Shiritori record. Check if the last character of the $i$th string is the same as the first character of the $i+1$th string, and check if there are no duplicate strings.


### Code (C++)

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

bool ok(vector<string> S)
{
    int N = S.size();
    for (int i = 0; i < N; i++)
        for (int j = 0; j < i; j++)
            if (S[i] == S[j])
                return false;
    for (int i = 0; i < N - 1; i++)
        if (S[i].back() != S[i + 1].front())
            return false;
    return true;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin >> N;
    vector<string> S(N);
    for (auto &x : S)
        cin >> x;

    int q = find(S.begin(), S.end(), "?") - S.begin();
    int M;
    cin >> M;
    for (int i = 0; i < M; i++)
    {
        cin >> S[q];
        if (ok(S))
            cout << S[q] << endl;
    }
}
```

### Code (Python)

```python
def ok(S):
    N = len(S)
    for i in range(N):
        for j in range(i):
            if S[i] == S[j]:
                return False
    for i in range(N - 1):
        if S[i][-1] != S[i + 1][0]:
            return False
    return True


def main():
    N = int(input())
    S = [input() for _ in range(N)]

    q = S.index("?")

    M = int(input())
    for _ in range(M):
        S[q] = input()
        if ok(S):
            print(S[q])


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

## Solution 2

Let's consider that `?` is the only thing that gets replaced in the Shiritori record. We should only be concerned about the parts related to `?`.

- The answer should start with the last character of the string before `?`.
- The answer should end with the first character of the string after `?`.
- The answer should not appear as a string in the Shiritori record.

### Code (C++)

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin >> N;
    vector<string> S(N);
    for (auto &x : S)
        cin >> x;

    int q = find(S.begin(), S.end(), "?") - S.begin();
    int M;
    cin >> M;
    for(int i=0; i<M; i++)
    {
        string a;
        cin >> a;
        if (find(S.begin(), S.end(), a) != S.end())
            continue;
        if (q != 0 && S[q - 1].back() != a.front())
            continue;
        if (q != N - 1 && a.back() != S[q + 1].front())
            continue;
        cout << a << endl;
    }
}
```

### Code (Python)

```python
def main():
    N = int(input())
    S = [input() for _ in range(N)]

    q = S.index("?")

    M = int(input())
    for _ in range(M):
        a = input()
        if a in S:
            continue
        if q != 0 and S[q - 1][-1] != a[0]:
            continue
        if q != N - 1 and a[-1] != S[q + 1][0]:
            continue
        print(a)


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


# Gerrymandering

## Solution 1

Ignore $0$ as it has no effect on the sum. Looking at the numbers from left to right, consider whether to include the number in the previous segment or to make it a new segment.

- If $A_i$ is positive, it's beneficial to create a new segment starting with $A_i$, except for cases where adding the number turns the sum of the segment from $0$ or less to greater than $0$.
- If $A_i$ is negative, it's beneficial to include $A_i$ in the previous segment, except for cases where adding the number turns the sum of the segment from greater than $0$ to $0$ or less.

After dividing into segments in this way, determine whether there are more positive segments than negative ones and print the result.

### Code (C++)

```cpp
#include <cinttypes>
#include <iostream>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--)
    {
        int N;
        cin >> N;
        int range_diff = 0;
        int64_t sum = 0;
        auto cut = [&]()
        {
            if (sum < 0)
                range_diff--;
            if (sum > 0)
                range_diff++;
            sum = 0;
        };
        for (int i = 0; i < N; i++)
        {
            int a;
            cin >> a;
            if ((sum > 0) + (a > 0) + (sum + a <= 0) >= 2)
                cut();
            sum += a;
        }
        cut();

        cout << (range_diff >= 1 ? "YES" : "NO") << '\n';
    }
}
```

### Code (Python)

```python
import sys


def solve(A):
    r = s = 0

    def cut():
        nonlocal r, s
        if s > 0:
            r += 1
        if s < 0:
            r -= 1
        s = 0

    for a in A:
        if (s > 0) + (a > 0) + (s + a <= 0) >= 2:
            cut()
        s += a
    cut()

    return r >= 1


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


def main():
    for _ in range(int(input())):
        N = input()
        *A, = map(int, input().split())
        print("YES" if solve(A) else "NO")


if __name__ == '__main__':
    main()

```

## Solution 2

Let $D_i$ be the maximum value when the number of positive segments minus the number of negative segments is viewed from $A_1, \cdots, A_i$.

- $D_0 = 0$
- $D_i = \max_{0 \le j < i} D_j + {\mathrm{sgn}}(A_{j+1} + \cdots + A_i)$

You can set up dynamic programming in this way. Here ${\mathrm {sgn}(x)}$ is $+1$ if $x$ is positive, $-1$ if it's negative, and $0$ if $x$ is zero.

Now, $A_1 + \cdots + A_i = S_i$, and the dynamic programming equation is as follows, divided according to the value of $\mathrm{sgn}$.

- $D_0 = 0$
- $D_i = \max_{0 \le j < i}\left[\max_{S_i < S_j}(D_j + 1), \max_{S_i=S_j} (D_j), \max_{S_i > S_j}(D_j-1) \right]$

This can be implemented using coordinate compression and segment trees.

### Code (C++)

```
<Working In Progress>
```

### Code (Python)

```
<Working In Progress>
```

# Same Range

## Solution

Let's think about the minimum $(i, j)$ pair where $\min(A_i, \cdots, j) = \min(B_i,, \cdots, B_j) = x$.

Assume that $A_x = k$, and let's think about the shape of $(i, j)$ that includes that number.

- For the minimum $f$ where $\min(A_f, \cdots, A_k), \min(B_f, \cdots, B_k) \ge x$ and the maximum $t$ where $\min(A_k, \cdots, A_t), \min(B_k, \cdots, B_t) \ge x$, if $i \in [f, k]; j \in [k, t]$ then $\min(A_i, \cdots, A_j) = x$, $\min(B_i, \cdots, B_j) \ge x$ are satisfied.
  - If you go beyond this range, it does not include $k$, or $\min(A_i, \cdots, A_j) <x$.
- Now, for the maximum $s$ and minimum $e$ that satisfy $B_s = x = B_e$ where $s \le k \le e$, if $i \in (s, k]; j \in [k, e)$ then $B_i, \cdots, B_j$ do not include $x$, so $\min(B_i, \cdots, B_j) > x$.

Thus, for the interval that includes $A_k = x$, the possible $(i, j)$ is $[f, t] \times [k, t] - (s, k] \times [k, e)$, and this can be expressed as the union of two rectangles. If you take the union for all $k = 1, \cdots, N$, the range of $(i, j)$ can be expressed as the union of up to $2N$ rectangles.

In the same way, after expressing $\max$ as a union of rectangles in the same way, you need to find the intersection of two ranges, the $\min$ shape and the $\max$ shape. This can be solved using a special form of segment tree.

### Code (C++)

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

struct Seg
{
    struct Node
    {
        int cnt12, cnt1, cnt2, col1, col2;
        Node() : cnt12(), cnt1(), cnt2(), col1(), col2() {}
        void recalc_leaf()
        {
            cnt12 = col1 && col2 ? 1 : 0;
            cnt1 = col1 ? 1 : 0;
            cnt2 = col2 ? 1 : 0;
        }
        void recalc_internal(const Node &L, const Node &R, int len)
        {
            cnt1 = col1 ? len : L.cnt1 + R.cnt1;
            cnt2 = col2 ? len : L.cnt2 + R.cnt2;
            cnt12 = col1 || col2 ? min(cnt1, cnt2) : L.cnt12 + R.cnt12;
        }
    };

    Seg(int n): N(1)
    {
        while (N < n)
            N *= 2;
        idx.resize(2 * N);
    };
    int getv() { return idx[1].cnt12; }
    void setv(int tp, int v, int s, int e)
    {
        function<void(int, int, int)> F = [&](int i, int l, int r)
        {
            if (e < l || r < s)
                return;
            if (s <= l && r <= e)
            {
                if (tp == 1)
                    idx[i].col1 += v;
                else
                    idx[i].col2 += v;
            }
            else
            {
                int m = (l + r) / 2;
                F(2 * i, l, m);
                F(2 * i + 1, m + 1, r);
            }
            if (i >= N)
                idx[i].recalc_leaf();
            else
                idx[i].recalc_internal(idx[2 * i], idx[2 * i + 1], r - l + 1);
        };
        F(1, 0, N - 1);
    }

private:
    int N;
    vector<Node> idx;
};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin >> N;
    vector<int> A(N), B(N);
    for (int &a : A)
        cin >> a;
    for (int &b : B)
        cin >> b;

    vector<int> C = A;
    copy(B.begin(), B.end(), back_inserter(C));
    sort(C.begin(), C.end());
    C.erase(unique(C.begin(), C.end()), C.end());
    int K = C.size();
    auto comp = [&](int x)
    { return distance(C.begin(), lower_bound(C.begin(), C.end(), x)); };

    set<int> smallB, largeB;
    vector<vector<int>> Aidx(K), Bidx(K), mnidx(K), mxidx(K);
    for (int i = 0; i < N; i++)
    {
        A[i] = comp(A[i]);
        B[i] = comp(B[i]);
        Aidx[A[i]].push_back(i);
        Bidx[B[i]].push_back(i);
        mnidx[min(A[i], B[i])].push_back(i);
        mxidx[max(A[i], B[i])].push_back(i);
        largeB.insert(i);
    }
    enum EventType
    {
        MIN_PUSH,
        MIN_POP,
        MAX_PUSH,
        MAX_POP
    };
    vector<vector<tuple<EventType, int, int>>> events(N + 1);
    for (int n = 0; n < K; n++)
    {
        for (int i : mxidx[n])
            largeB.erase(i);

        for (int i : Aidx[n])
        {
            int left_same = -1, left_large = -1, left_small = -1;
            int right_same = N, right_large = N, right_small = N;

            auto vit = upper_bound(Bidx[n].begin(), Bidx[n].end(), i);
            if (vit != Bidx[n].begin())
                left_same = *prev(vit);
            vit = lower_bound(Bidx[n].begin(), Bidx[n].end(), i);
            if (vit != Bidx[n].end())
                right_same = *vit;

            auto sit = largeB.upper_bound(i);
            if (sit != largeB.begin())
                left_large = *prev(sit);
            sit = largeB.lower_bound(i);
            if (sit != largeB.end())
                right_large = *sit;

            sit = smallB.upper_bound(i);
            if (sit != smallB.begin())
                left_small = *prev(sit);
            sit = smallB.lower_bound(i);
            if (sit != smallB.end())
                right_small = *sit;

            if (left_large < left_same && i < right_large)
            {
                events[i].emplace_back(MAX_PUSH, left_large + 1, left_same);
                events[right_large].emplace_back(MAX_POP, left_large + 1, left_same);
            }
            if (left_large < i && right_same < right_large)
            {
                events[right_same].emplace_back(MAX_PUSH, left_large + 1, i);
                events[right_large].emplace_back(MAX_POP, left_large + 1, i);
            }

            if (left_small < left_same && i < right_small)
            {
                events[i].emplace_back(MIN_PUSH, left_small + 1, left_same);
                events[right_small].emplace_back(MIN_POP, left_small + 1, left_same);
            }
            if (left_small < i && right_same < right_small)
            {
                events[right_same].emplace_back(MIN_PUSH, left_small + 1, i);
                events[right_small].emplace_back(MIN_POP, left_small + 1, i);
            }
        }

        for (int i : mnidx[n])
            smallB.insert(i);
    }

    int64_t ans = 0;
    Seg seg(N);
    for (int i = 0; i < N; i++)
    {
        for (auto [ev, s, e] : events[i])
            seg.setv(ev == MIN_PUSH || ev == MIN_POP ? 1 : 2, ev == MIN_PUSH || ev == MAX_PUSH ? +1 : -1, s, e);
        ans += seg.getv();
    }

    cout << ans << endl;
}
```

### Code (Python)

```
<Working In Progress>
```


# Avoiding Multiples

## Solution

If $X+Y$ is a multiple of $K$ and the remainder when $X$ is divided by $K$ is $i$, it can be noted that the remainder when $Y$ is divided by $K$ must be $(K-i) \bmod K$.

Let $C_j$ be the count of $A_i$ whose remainder is $j$ when divided by $K$.

- For $v = 1, \cdots, \lceil \frac K 2 \rceil -1$, the number of cases choosing numbers with a remainder of $v$ or $K-v$
  - The number that adds up to a multiple of $K$ with $v$ is $K-v$. In other words, $S$ must only contain numbers whose remainder, when divided by $K$ is $v$ or $K-v$.
  - The number of cases where a number with a remainder of $v, K-v$ when divided by $K$ is included in $S$ is $2^{C_v} -1$ and $2^{C_{K-v}}-1$ respectively, and the case where neither number is included is $1$. Therefore, the number of cases choosing this remainder is $2^{C_v} + 2^{C_{K-v}} - 1$.
- For $v = 0$ or when $K$ is a multiple of $2$ and $v = \frac K 2$
  - The number that becomes a multiple of $K$ when met with $v$ is $v$. So, at most single number with a remainder of $v$ can be included. The number of such cases is $C_v + 1$.

The answer is the product of all number of cases to choose each remainder.

### Code (C++)

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

const int MOD = 1e9 + 7;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N, K;
    cin >> N >> K;
    vector<int> c(K);
    for (int i = 0; i < N; i++)
    {
        int a;
        cin >> a;
        c[a % K]++;
    }
    int ans = 1;
    for (int i = 1; i < (K + 1) / 2; i++)
    {
        int pi = 1, pj = 1;
        for (int k = 0; k < c[i]; k++)
            pi = pi * 2 % MOD;
        for (int k = 0; k < c[K - i]; k++)
            pj = pj * 2 % MOD;
        ans = (int64_t)ans * (pi + pj - 1) % MOD;
    }
    ans = (int64_t)ans * (c[0] + 1) % MOD;
    if (K % 2 == 0)
        ans = (int64_t)ans * (c[K / 2] + 1) % MOD;

    ans = (ans + MOD - (N + 1)) % MOD;
    cout << ans << endl;
}
```

### Code (Python)

```python
import sys


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


def main():

    MOD = 10**9 + 7
    N, K = map(int, input().split())
    c = [0]*K
    *A, = map(int, input().split())
    for a in A:
        c[a % K] += 1

    ans = 1
    for i in range(1, (K + 1) // 2):
        ans = ans * (pow(2, c[i], MOD) + pow(2, c[K-i], MOD) - 1) % MOD

    ans = ans * (c[0] + 1) % MOD
    if K % 2 == 0:
        ans = ans * (c[K // 2] + 1) % MOD
    ans = (ans - (N + 1)) % MOD
    print(ans)


if __name__ == "__main__":
    main()

```

# Moving Stones

## Solution

The basic idea is to count how many turns one can move their team's stone without giving the other team an extra turn.

Let's look at the stones one by one from the back. Without loss of generality, let's say the stone at the very back is `B`.

- This stone can be moved forward without giving the white team an extra turn, so if it can be moved, it's advantageous to do so. Similarly, stones before `W` appears can also be moved.
- The first `W` stone seen from the back should not be moved, as moving this `W` stone one step forward allows `B` to gain an extra turn by moving the `B` stone behind it one step forward.

Now after counting the total moves that `B` can move in `WBBB...` at the very back, exclude all these stones and move forward to determine the number of movable stones for the rest.

### Code (C++)

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

bool solve(string s)
{
    int64_t move = 0, cnt = 0;
    char cur = '.';

    reverse(s.begin(), s.end());
    for (char c : s)
    {
        if (cur == '.')
            cur = c;
        if (cur == '.')
            continue;
        if (c == '.')
            move += (cur == 'W' ? +1 : -1) * cnt;
        else if (c == cur)
            cnt++;
        else
            cur = '.', cnt = 0;
    }
    return move > 0;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--)
    {
        string s;
        cin >> s;
        cout << (solve(s) ? "WHITE" : "BLACK") << '\n';
    }
}
```

### Code (Python)

```python
import sys


def solve(s):
    move, cnt, cur = 0, 0, '.'
    for c in s[::-1]:
        if cur == '.':
            cur = c
        if cur == '.':
            continue
        if c == '.':
            move += (1 if cur == 'W' else -1) * cnt
        elif c == cur:
            cnt += 1
        else:
            cnt, cur = 0, '.'

    return move > 0


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


def main():
    for _ in range(int(input())):
        print("WHITE" if solve(input()) else "BLACK")


if __name__ == '__main__':
    main()

```


# Making Sticks

## Solution

The number of ways to make a rod of length $i$ is to use a rod of length $i$ as it is or to stretch a rod of length that is a divisor of $i$ by $k$ times.

That is, if the number of $v$ with $A_v = i$ is $C_i$, then $D_i = C_i + \sum_{1 \le j < i;\ j \mid i} D_j$.

This can be obtained with a time complexity of $O(K \sqrt K)$ or $O(K \log K)$ depending on the implementation.

## Implementation 1

If you use a method to find all divisors of $X$ in $O(\sqrt X)$ time, the solution will be in $O(K \sqrt K)$ time.

### Code (C++)

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

int main()
{
    int N, Q;
    cin >> N;
    vector<int> A(N);
    for (int &a : A)
        cin >> a;
    cin >> Q;
    vector<int> L(Q);
    for (int &l : L)
        cin >> l;

    int MX = max(*max_element(A.begin(), A.end()), *max_element(L.begin(), L.end()));
    vector<int64_t> D(MX + 1);
    for (int a : A)
        D[a]++;

    for (int i = 2; i <= MX; i++)
        for (int j = 1; j * j <= i; j++)
            if (i % j == 0)
            {
                D[i] += D[j];
                if (j * j != i && j != 1)
                    D[i] += D[i / j];
            }
    for (int l : L)
        cout << D[l] << ' ';
    cout << endl;
}
```

### Code (Python)

```python
from itertools import count
import sys


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


def main():
    N = int(input())
    A = list(map(int, input().split()))
    Q = int(input())
    L = list(map(int, input().split()))

    MX = max(max(A), max(L))
    D = [0] * (MX + 1)
    for a in A:
        D[a] += 1

    for i in range(2, MX + 1):
        for j in count(1):
            if j * j > i:
                break
            if i % j == 0:
                D[i] += D[j]
                if j * j != i and j != 1:
                    D[i] += D[i // j]

    print(*(D[i] for i in L))


if __name__ == '__main__':
    main()

```

## Implementation 2

Counting multiples is easier than counting divisors. If you increase $j$ from $1$, after the calculation of $D_j$ is completed, add $D_j$ to $D_i$ for the multiple $i$ of $j$. By implementing this, you can solve it in $O\left(\frac K 1 + \frac K 2 + \cdots + \frac K K = K \log K\right)$ time.

### Code (C++)

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

int main()
{
    int N, Q;
    cin >> N;
    vector<int> A(N);
    for (int &a : A)
        cin >> a;
    cin >> Q;
    vector<int> L(Q);
    for (int &l : L)
        cin >> l;

    int MX = max(*max_element(A.begin(), A.end()), *max_element(L.begin(), L.end()));
    vector<int64_t> D(MX + 1);
    for (int a : A)
        D[a]++;

    for (int j = 1; j <= MX; j++)
        for (int i = 2 * j; i <= MX; i += j)
            D[i] += D[j];
    for (int l : L)
        cout << D[l] << ' ';
    cout << endl;
}
```

### Code (Python)

```python
import sys


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


def main():
    N = int(input())
    A = list(map(int, input().split()))
    Q = int(input())
    L = list(map(int, input().split()))

    MX = max(max(A), max(L))
    D = [0] * (MX + 1)
    for a in A:
        D[a] += 1

    for j in range(1, MX + 1):
        for i in range(2 * j, MX + 1, j):
            D[i] += D[j]

    print(*(D[i] for i in L))


if __name__ == '__main__':
    main()

```



# Matrix Operations (Calculate the Matrix)

## Solution

An operation that changes the number in the $r$'th row and $c$'th column of the matrix is one of the following two operations.

1. Add $v$ to the $r$'th row.
2. Add $v$ to the $c$'th column.

Therefore, the number in the $r$'th row and $c$'th column is the sum of the total numbers added to the $r$'th row and the $c$'th column.

This can solve the problem by accumulating the total added values for each row and column.

### Code (C++)

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N, M, Q;
    cin >> N >> M >> Q;
    vector<int> R(N), C(M);
    for (int i = 0; i < Q; i++)
    {
        int t, rc, v;
        cin >> t >> rc >> v;
        if (t == 1)
            R[rc - 1] += v;
        else
            C[rc - 1] += v;
    }
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
            cout << R[i] + C[j] << ' ';
        cout << '\n';
    }
}
```

### Code (Python)

```python
import sys


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


def main():
    N, M, Q = map(int, input().split())
    R = [0] * N
    C = [0] * M
    for _ in range(Q):
        t, rc, v = map(int, input().split())
        if t == 1:
            R[rc - 1] += v
        else:
            C[rc - 1] += v
    for i in range(N):
        for j in range(M):
            print(R[i] + C[j], end=' ')
        print()


if __name__ == "__main__":
    main()

```


# Matrix Operations (Find Operations)

## Solution

An operation that changes the number in the $r$'th row and $c$'th column of the matrix is one of the following two operations:

1. Add $v$ to the $r$'th row.
2. Add $v$ to the $c$'th column.

In other words, the number in the $r$'th row and $c$'th column is the sum of the total numbers added to the $r$'th row and the $c$'th column.

Now, let's call the number added to the first row $x$.

- The sum of the number added to the first row and the number added to the $c$'th column must be $A_{1, c}$, so the number added to the $c$'th column must be $A_{1, c} - x$.
- The sum of the number added to the $r$'th row and the first column must be $A_{r, 1}$, so the number added to the $r$'th row must be $x + (A_{r, 1} - A_{1, 1})$.

Since we want to minimize the number of operations, we need to make the numbers added to each row or column as $0$ as much as possible. To do this, if you choose $x$ as the most frequent number among all $A_{1, c}$ and $A_{1,1} - A_{r, 1}$, you can make the number of $0$s to be added to each row or column as many as possible.

After deciding $x$ and calculating the numbers to be added to each row and column, you can check if the actual operations are performed to match the $A$ array.

### Code (C++)

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N, M;
    cin >> N >> M;
    vector<vector<int>> A(N, vector<int>(M));
    for (auto &y : A)
        for (int &x : y)
            cin >> x;

    map<int, int> cnt;
    for (int i = 0; i < N; i++)
        cnt[A[0][0] - A[i][0]]++;
    for (int i = 0; i < M; i++)
        cnt[A[0][i]]++;
    int mxv = 0, mxc = 0;
    for (auto [v, c] : cnt)
        if (mxc < c)
            mxv = v, mxc = c;

    vector<int> R(N), C(M);
    for (int i = 0; i < N; i++)
        R[i] = mxv + A[i][0] - A[0][0];
    for (int i = 0; i < M; i++)
        C[i] = A[0][i] - mxv;

    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            if (R[i] + C[j] != A[i][j])
            {
                cout << -1 << endl;
                return 0;
            }

    cout << N + M - mxc << '\n';
    for (int i = 0; i < N; i++)
        if (R[i])
            cout << 1 << " " << i + 1 << " " << R[i] << '\n';
    for (int i = 0; i < M; i++)
        if (C[i])
            cout << 2 << " " << i + 1 << " " << C[i] << '\n';
}
```

### Code (Python)

```python
import sys
from collections import defaultdict


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


def main():
    N, M = map(int, input().split())
    A = [list(map(int, input().split())) for i in range(N)]

    cnt = defaultdict(int)
    for i in range(N):
        cnt[A[0][0] - A[i][0]] += 1
    for i in range(M):
        cnt[A[0][i]] += 1

    mxv = mxc = 0
    for v, c in cnt.items():
        if mxc < c:
            mxv, mxc = v, c

    R = [mxv+A[i][0] - A[0][0] for i in range(N)]
    C = [A[0][i] - mxv for i in range(M)]

    for i in range(N):
        for j in range(M):
            if R[i] + C[j] != A[i][j]:
                print(-1)
                return

    print(N + M - mxc)
    for i in range(N):
        if R[i]:
            print(1, i + 1, R[i])
    for i in range(M):
        if C[i]:
            print(2, i + 1, C[i])


if __name__ == '__main__':
    main()

```

