## 题目描述

The main street of Berland’s capital is a segment with length $s$. The main street has traffic lights installed along it. The traffic lights have been functioning since time immemorial, cyclically changing colors from red to green and vice versa. Each traffic light can be described by four numbers $x_i, r_i, g_i, d_i$, which stand for:

• $x_i$ – the distance from the beginning of the street to the traffic light ($1 \le x_i \lt s$),
• $r_i$ – the duration of the red light illumination ($10 \le r_i \le 20$),
• $g_i$ – the duration of the green light illumination ($10 \le g_i \le 20$),
• $d_i$ – the minimum non-negative moment of time when the traffic light changes the light from green to red ($0 \le d_i \lt r_i+g_i$).

Each traffic light retains its light cycle from the ancient past.
The King of Berland asked the transport minister to customize the traffic lights according to a “green wave” principle. That means that if you start driving from the beginning of the street at the recommended speed, you can drive through the entire street without stopping, that is, you pass each traffic light when it has the green light on.
Now it is time to show the “green wave” to the King, but the work is not even started yet. You may assume that the King starts driving at the moment of time $0$ from the beginning of the street. So the minister decided to choose some speed $v_0$ and tell the king that the “green wave” works specifically for this speed. Moreover, they can switch any number of traffic lights to the “always green” mode. The minister’ aim is to ensure that if the King drives through the street at the recommended speed $v_0$ he encounters no red traffic light. Driving exactly at the moment when the colors are changed is not considered driving through the red light.
Any transport’s maximum speed is limited in Berland: it should not exceed $v_{\max}$. On the other hand, the King will be angry if the recommended speed is less than $v_{\min}$. Thus, the minister should choose such value of $v_0$, which satisfies the inequation $v_{\min} \le v_0 \le v_{\max}$.
Help the minister to find such $v_0$ value, that the number of traffic lights to switch to the “always green” mode is minimum. If $v_0$ is not uniquely defined, choose the maximum possible value of $v_0$.

## 代码

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstring>

static int const N = 20005;
static double const EPS = 1e-12;

int pm(double const &n) {
return fabs(n) < EPS ? 0 : n < 0 ? -1 : 1;
}

std::bitset<N> ans, cur;
struct Query {
int id, op;
double x;
friend bool operator<(Query const &a, Query const &b) {
return pm(a.x - b.x) ? !~pm(a.x - b.x) : a.op < b.op;
}
} itv[N * 100];

int main() {
int n, s, vmn, vmx, top = 0;
scanf("%d%d%d%d", &n, &s, &vmn, &vmx);
for (int i = 0, x, r, g, d; i < n; ++i) {
scanf("%d%d%d%d", &x, &r, &g, &d);
if (d > g) {
double l = 1. * x / (d - g);
itv[top++] = (Query){i, 1, l};
}
for (;; d += r + g) {
double l = 1. * x / (d + r), r = d ? 1. * x / d : 1e9;
if (pm(r - vmn) < 1) {
break;
}
if (pm(vmx - l) < 1) {
continue;
}
itv[top++] = (Query){i, 1, l}, itv[top++] = (Query){i, -1, r};
}
}
itv[top++] = (Query){n, 1, 0. + vmx};
std::sort(itv, itv + top);
int ac = n, cc = 0;
double vc = 0;
for (int i = 0; i < n; ++i) {
ans.set(i);
}
for (int i = 0; i < top && pm(itv[i].x - vmx) < 1; ++i) {
if (itv[i].op == 1) {
if (cc <= ac && pm(vmn - itv[i].x) < 1) {
ans = cur, ac = cc, vc = itv[i].x;
}
if (itv[i].id < n) {
cur.set(itv[i].id), ++cc;
}
} else {
cur.reset(itv[i].id), --cc;
}
}
printf("%.10lf\n%d\n", vc, ac);
for (int i = 0; i < n; ++i) {
if (ans.test(i)) {
printf("%d ", i + 1);
}
}
puts("");
return 0;
}


## 题目描述

Let’s consider a string of non-negative integers, containing $N$ elements. Suppose these elements are $S_1, S_2, \ldots, S_N$, in the order in which they are placed inside the string. Such a string is called ‘funny’ if the string $S_1+1, S_2, S_3, \ldots, S_{N-1}, S_N-1$ can be obtained by rotating the first string (to the left or to the right) several times. For instance, the strings $2, 2, 2, 3$ and $1, 2, 1, 2, 2$ are funny, but the string $1, 2, 1, 2$ is not. Your task is to find a funny string having $N$ elements, for which the sum of its elements $S_1+S_2+ \cdots +S_N$ is equal to $K$.

## 算法分析

0_______1（旧）
1_______0（新）

0______11
1______10

0____1_11
1____1_10

0__1_1_11
1__1_1_10

01_1_1_11
11_1_1_10

010101011
110101010

## 代码

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct IOManager {
template <typename T> inline bool read(T &x) { char c = '\n'; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; c == '-' && (flag = true, c = getchar()); if (! ~ c) return false; while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); }
inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; }
inline int read(char s[]) { char c = '\n'; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return 0; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', len); }
template <typename T> inline IOManager operator > (T &x) { read(x); return *this; }
template <typename T> inline void write(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) write(x / 10); putchar(x % 10 + '0'); }
inline void write(char c) { putchar(c); }
inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); }
template <typename T> inline IOManager operator < (T x) { write(x); return *this; }
} io;

struct Solver {
private:
static const int N = 1010;
int n, k, a[N];
void input() { io > n > k; }
void init() {
int t = k / n;
for (int i = 1; i <= n; ++ i) a[i] = t, k -= t;
}
void process() {
int sum = n - 1;
while (sum % k) sum += n;
int p = sum / k + 1;
for (; p < n; p = (p - 1 + sum / k) % n + 1) ++ a[p]; ++ a[n];
for (int i = 1; i <= n; ++ i) io < a[i] < ' ';
io < '\n';
}

public:
void solve() { input(), init(), process(); }
} solver;

int main() {
solver.solve();
return 0;
}


## 题目描述

There is a syntactically correct boolean expression.
The definition of syntactically correct expression follows as:

1. “a”, “b”, “c”, …, “j” are syntactically correct expressions.
2. If A is a correct expression, then !A and (A) are correct expressions too.
3. If A is a correct expression and B is a correct expression, then A||B, A&B, A<=>B, A=>B, A#B are syntactically correct expressions too.

Syntactically correct expression doesn’t contain spaces.
Small Latin letters are variables, ! denotes negation, || – disjunction, & – conjunction, <=> – equality, => – implication, # – excepting or.
Negation has the highest priority, conjunction has middle priority, and other operations have low priority. Brackets change the order of operations executing.
Two expressions are called identical if their values are the same in any values of variables.
Make the expression, which will be identical with given expression. New expression must be free of brackets.

## 代码

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <stack>

using namespace std;

struct Solver {
private:
string s;
void input() { cin >> s; }
int len(char c) {
switch (c) {
case '!' : return 0;
case '&' : return 0;
case '|' : return 1;
case '<' : return 2;
case '=' : return 1;
case '#' : return 0;
}
}
int priority(char c) {
switch (c) {
case '!' : return 1;
case '&' : return 2;
case '|' : return 3;
case '<' : return 3;
case '=' : return 3;
case '#' : return 3;
case '(' : return 4;
}
}
bool single(bool a, char c, bool b) {
switch (c) {
case '&' : return a && b;
case '|' : return a || b;
case '<' : return a == b;
case '=' : return a || ! b;
case '#' : return a ^ b;
}
}
int match(string s, int p) {
int cnt = 1;
while (cnt) ++ p, cnt += (s[p] == '(') - (s[p] == ')');
return p;
}
stack <char> symbol;
stack <bool> number;
void pop() {
if (symbol.top() == '!') {
symbol.pop(); bool p = number.top(); number.pop(), number.push(! p);
} else {
bool p = number.top(); number.pop();
bool q = number.top(); number.pop();
number.push(single(p, symbol.top(), q));
symbol.pop();
}
}
bool calc(string s) {
for (int i = 0; i < s.length(); ++ i) {
if (isdigit(s[i])) number.push(s[i] - '0');
else if (s[i] == '(') symbol.push('(');
else if (s[i] == ')') {
while (symbol.top() != '(') pop();
symbol.pop();
} else {
while (! symbol.empty() && priority(symbol.top()) <= priority(s[i])) pop();
symbol.push(s[i]), i += len(s[i]);
}
}
while (! symbol.empty()) pop();
return number.top();
}
bool check(int p, string s) {
for (int i = 0; i < s.length(); ++ i)
if (isalpha(s[i])) s[i] = ((p & 1 << s[i] - 'a') > 0) + '0';
return calc(s);
}
void process() {
for (int i = 0; i + 1 < s.length(); ++ i)
while (i + 1 < s.length() && s[i] == '!' && s[i + 1] == '!')
s = s.substr(0, i) + s.substr(i + 2);
string ans, sep;
for (int i = 0; i < 1 << 10; ++ i)
if (check(i, s)) {
ans += sep, sep = "||";
string s;
for (int j = 0; j < 10; ++ j) {
ans += s, s = "&";
if (! (i & 1 << j)) ans += "!";
ans += j + 'a';
}
}
if (ans.length() == 0) ans = "!a&a";
cout << ans << endl;
}

public:
void solve() { input(), process(); }
} solver;

int main() {
solver.solve();
return 0;
}


## 题目描述

There are $N$ points given by their coordinates on a plane. All coordinates $(x_i, y_i)$ are integers in a range from $-10000$ up to $10000$ inclusive . It is necessary to construct a broken line satisfying the following conditions:

• The broken line should be closed.
• End points of each segment (verteces) of the broken line can only be the given points, and all given points should be used.
• Each two consecutive segments of the broken line should form a corner of 90 degrees in each vertex point.
• The sides of the broken line should be parallel to coordinate axes.
• The broken line should have no self-crossing and self-contact.
• The broken line should have the minimal length.

You have to either find the length $L$ of the constructed broken line, or determine that it is impossible to construct such a broken line.

## 题意概述

• 这个图形是闭合的；
• 每条边的端点必须是给定的点，且每个给定的点必须被用到；
• 每个点连接的两条边必须互相垂直；
• 每条边必须平行于坐标轴；
• 任意两条边除了顶点外不能相交；
• 这个图形的周长最小。

## 代码

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct IOManager {
template <typename T> inline bool read(T &x) { char c = '\n'; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; c == '-' && (flag = true, c = getchar()); if (! ~ c) return false; while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); }
inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; }
inline int read(char s[]) { char c = '\n'; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return 0; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', len); }
template <typename T> inline IOManager operator > (T &x) { read(x); return *this; }
template <typename T> inline void write(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) write(x / 10); putchar(x % 10 + '0'); }
inline void write(char c) { putchar(c); }
inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); }
template <typename T> inline IOManager operator < (T x) { write(x); return *this; }
} io;

struct Point { int x, y, id; };

bool cmpx(Point a, Point b) { return a.x == b.x ? a.y < b.y : a.x < b.x; }
bool cmpy(Point a, Point b) { return a.y == b.y ? a.x < b.x : a.y < b.y; }
bool cmpi(Point a, Point b) { return a.id < b.id; }

struct Line { Point a, b; };

struct Solver {
private:
static const int N = 10010;
int n, top, fa[N];
Point point[N];
Line line[N];
void input() {
io > n;
for (int i = 1; i <= n; ++ i) io > point[i].x > point[i].y, point[i].id = i;
}
bool inter(Line p, Line q) {
if (p.a.x == p.b.x && q.a.x == q.b.x) {
if (p.a.y > q.a.y) swap(p, q);
if (p.a.x != q.a.x) return false;
else return p.b.y > q.a.y;
} else if (p.a.y == p.b.y && q.a.y == q.b.y) {
if (p.a.x > q.a.x) swap(p, q);
if (p.a.y != q.a.y) return false;
else return p.b.x > q.a.x;
} else {
if (p.a.x != p.b.x) swap(p, q);
return p.a.y < q.a.y && q.a.y < p.b.y && q.a.x < p.a.x && p.a.x < q.b.x;
}
}
int get_fa(int t) { return t == fa[t] ? t : fa[t] = get_fa(fa[t]); }
void process() {
int l = 0, r = 0, cnt = n - 1;
sort(point + 1, point + n + 1, cmpx);
for (int i = 1; i <= n; i = r) {
l = i, r = i + 1;
while (r <= n && point[r].x == point[l].x) ++ r;
if (r - l & 1) { io < 0 < '\n'; return; }
for (int j = l; j < r; j += 2) line[++ top] = (Line) { point[j], point[j + 1] };
}
sort(point + 1, point + n + 1, cmpy);
for (int i = 1; i <= n; i = r) {
l = i, r = i + 1;
while (r <= n && point[r].y == point[l].y) ++ r;
if (r - l & 1) { io < 0 < '\n'; return; }
for (int j = l; j < r; j += 2) line[++ top] = (Line) { point[j], point[j + 1] };
}
sort(point + 1, point + n + 1, cmpi);
for (int i = 1; i <= top; ++ i)
if (line[i].a.x > line[i].b.x || line[i].a.y > line[i].b.y) swap(line[i].a, line[i].b);
for (int i = 1; i < top; ++ i)
for (int j = i + 1; j <= top; ++ j)
if (inter(line[i], line[j])) { io < 0 < '\n'; return; }
for (int i = 1; i <= n; ++ i) fa[i] = i;
for (int i = 1; i <= top; ++ i) {
int p = get_fa(line[i].a.id), q = get_fa(line[i].b.id);
if (p != q) fa[p] = q, -- cnt;
}
if (cnt) { io < 0 < '\n'; return; }
int ans = 0;
for (int i = 1; i <= top; ++ i) ans += line[i].b.x - line[i].a.x + line[i].b.y - line[i].a.y;
io < ans < '\n';
}

public:
void solve() { input(), process(); }
} solver;

int main() {
solver.solve();
return 0;
}


## 题目描述

There are two boxes. There are $A$ balls in the first box, and $B$ balls in the second box. It is possible to move balls from one box to another. From one box into another one should move as many balls as the other box already contains. You have to determine, whether it is possible to move all balls into one box.

## 题目描述

Farmer John has just given the cows a program to play with! The program contains two integer variables, $x$ and $y$, and performs the following operations on a sequence $a_1, a_2, \ldots, a_n$ of positive integers:

1. Initially, $x=1$ and $y=0$. If, after any step, $x \le 0$ or $x \gt n$, the program immediately terminates.
2. The program increases both $x$ and $y$ by a value equal to $a_x$ simultaneously.
3. The program now increases $y$ by $a_x$ while decreasing $x$ by $a_x$.
4. The program executes steps 2 and 3 (first step 2, then step 3) repeatedly until it terminates (it may never terminate). So, the sequence of executed steps may start with: step 2, step 3, step 2, step 3, step 2 and so on.

The cows are not very good at arithmetic though, and they want to see how the program works. Please help them!
You are given the sequence $a_2, a_3, \ldots, a_n$. Suppose for each $i \; (1 \le i \le n-1)$ we run the program on the sequence $i, a_2, a_3, \ldots, a_n$. For each such run output the final value of $y$ if the program terminates or $-1$ if it does not terminate.

## 题意概述

while (!(x <= 0 || x > n)) {
y += a[x], x += a[x];
if (!(x <= 0 || x > n)) y += a[x], x -= a[x];
}


## 代码

#include <iostream>
using namespace std;
long long n, a[300001], ans[300001][2], to[300001][2], vis[300001][2];
long long dfs(long long t, long long m) {
if (ans[t][m]) return ans[t][m];
if (vis[t][m]) return ans[t][m] = -1; vis[t][m] = true;
if (to[t][m] < 1 || to[t][m] > n) return ans[t][m] = a[t];
long long ret = dfs(to[t][m], !m);
if (ret == -1) ans[t][m] = -1; else ans[t][m] = a[t] + ret;
return ans[t][m];
}
int main()
{
cin >> n, vis[1][1] = true;
for (int i = 2; i <= n; ++i) cin >> a[i];
for (int i = 2; i <= n; ++i) to[i][0] = i - a[i], to[i][1] = i + a[i];
for (int i = 2; i <= n; ++i) if (!ans[i][0]) dfs(i, 0);
for (int i = 1; i < n; ++i)
if (ans[i + 1][0] == -1) cout << -1 << endl;
else cout << i + ans[i + 1][0] << endl;
return 0;
}


## 题目描述

Vasily has a deck of cards consisting of $n$ cards. There is an integer on each of the cards, this integer is between $1$ and $100000$, inclusive. It is possible that some cards have the same integers on them.
Vasily decided to sort the cards. To do this, he repeatedly takes the top card from the deck, and if the number on it equals the minimum number written on the cards in the deck, then he places the card away. Otherwise, he puts it under the deck and takes the next card from the top, and so on. The process ends as soon as there are no cards in the deck. You can assume that Vasily always knows the minimum number written on some card in the remaining deck, but doesn’t know where this card (or these cards) is.
You are to determine the total number of times Vasily takes the top card from the deck.

## 代码

#include <iostream>
#include <vector>
using namespace std;
struct binary_indexed_tree {
long long n; vector<long long> a;
void init(long long t) { n = t + 10, a.clear(), a.resize(n); }
void add(long long p, long long t) {
for (long long i = p; i < n; i += i & -i) a[i] += t;
}
long long sum(long long p) {
long long ret = 0;
for (long long i = p; i; i -= i & -i) ret += a[i];
return ret;
}
} tree;
long long n, t, now, ans, pre;
vector<long long> b[100001];
int main()
{
cin >> n;
tree.init(n);
for (long long i = 1; i <= n; ++i) {
cin >> t; tree.add(i, 1), b[t].push_back(i);
}
for (long long i = 1; i <= 100000; ++i) {
if (!b[i].size()) continue; long long pnt = 0;
while (pnt < b[i].size() && b[i][pnt] < now) ++pnt; --pnt;
if (pnt < 0) pnt = b[i].size() - 1;
if (b[i][pnt] > now) ans += tree.sum(b[i][pnt]) - tree.sum(now);
else ans += tree.sum(n) - tree.sum(now) + tree.sum(b[i][pnt]);
for (long long j = 0; j < b[i].size(); ++j) tree.add(b[i][j], -1);
now = b[i][pnt];
}
cout << ans << endl;
return 0;
}


## 题目描述

Ivan had string $s$ consisting of small English letters. However, his friend Julia decided to make fun of him and hid the string $s$. Ivan preferred making a new string to finding the old one.
Ivan knows some information about the string $s$. Namely, he remembers, that string $t_i$ occurs in string $s$ at least $k_i$ times or more, he also remembers exactly $k_i$ positions where the string $t_i$ occurs in string $s$: these positions are $x_{i, 1}, x_{i, 2}, \ldots, x_{i, k_i}$. He remembers $n$ such strings $t_i$.
You are to reconstruct lexicographically minimal string $s$ such that it fits all the information Ivan remembers. Strings $t_i$ and string $s$ consist of small English letters only.

## 代码

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
string s[100001];
struct cons {
int n, p;
bool operator < (const cons &a) const {
return p > a.p ? true : p == a.p ? s[n].length() > s[a.n].length() : false;
}
} con[1000001];
int n, c, p, l, len, ma, top, pre[2000001], nxt[2000001];
char str[2000001];
int main()
{
scanf("%d", &n);
for (int i = 1; i <= 2000000; ++i) pre[i] = i - 1, nxt[i] = i + 1;
for (int i = 1; i <= n; ++i) {
cin >> s[i]; scanf("%d", &c);
for (int j = 1; j <= c; ++j) {
scanf("%d", &p), con[++top].n = i, con[top].p = p;
}
}
sort(con + 1, con + top + 1);
for (int i = 1; i <= top; ++i) {
if (con[i].p == con[i - 1].p) continue;
l = len = s[con[i].n].length(), p = con[i].p;
while (l > 0) {
ma = max(ma, p), str[p] = s[con[i].n][len - l];
nxt[pre[p]] = nxt[p];
pre[nxt[p]] = pre[p];
l -= nxt[p] - p, p = nxt[p];
}
}
for (int i = 1; i <= ma; ++i) {
if (str[i] >= 'a' && str[i] <= 'z') printf("%c", str[i]);
else printf("a");
}
printf("\n");
return 0;
}


## 题目描述

Chef found a strange string yesterday – a string of signs $s$, where each sign is either a ‘<‘, ‘=’ or a ‘>’. Let $N$ be the length of this string. Chef wants to insert $N+1$ positive integers into this sequence and make it valid. A valid sequence is a sequence where every sign is preceded and followed by an integer, and the signs are correct. That is, if a sign ‘<‘ is preceded by the integer $a$ and followed by an integer $b$, then $a$ should be less than $b$. Likewise for the other two signs as well.
Chef can take some positive integers in the range $[1, P]$ and use a number in the range as many times as he wants.
Help Chef find the minimum possible $P$ with which he can create a valid sequence.

## 算法分析

‘=’对最终结果没有影响，可以全部忽略。设找到了一个只由'<‘或’>’组成的最长连续子串，长度为$l$。在这个子串的左边填入$a$，右边填入$a+l$。由于其他只由'<‘或’>’组成的连续子串的长度均不大于$l$，因此也可以分别在它们左右填入$a$和$a+l$，这样必定可以满足题目要求。

## 代码

#include <iostream>
#include <algorithm>
using namespace std;
int n, ans, len, out;
string s;
int main()
{
cin >> n;
while (n--) {
cin >> s;
ans = out = 0;
len = s.length();
for (int i = 0; i < len; ++i) {
if (s[i] == '<') {
if (ans < 0) ans = 0;
++ans;
}
if (s[i] == '>') {
if (ans > 0) ans = 0;
--ans;
}
out = max(out, abs(ans) + 1);
}
cout << out << endl;
}
return 0;
}


## 题目描述

On the way to school, Karen became fixated on the puzzle game on her phone!
The game is played as follows. In each level, you have a grid with $n$ rows and $m$ columns. Each cell originally contains the number $0$.
One move consists of choosing one row or column, and adding $1$ to all of the cells in that row or column.
To win the level, after all the moves, the number in the cell at the $i$-th row and $j$-th column should be equal to $g_{i, j}$.
Karen is stuck on one level, and wants to know a way to beat this level using the minimum number of moves. Please, help her with this task!

## 代码

#include <iostream>
using namespace std;
int n, m, p, q, top, f, a[101][101], ans[100001], mode[100001];
bool check(int t, int mode) {
if (!mode) {
for (int i = 1; i <= m; ++i) if (!a[t][i]) return false;
for (int i = 1; i <= m; ++i) --a[t][i];
return true;
} else {
for (int i = 1; i <= n; ++i) if (!a[i][t]) return false;
for (int i = 1; i <= n; ++i) --a[i][t];
return true;
}
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
cin >> a[i][j];
}
}
p = n, q = m;
if (p > q) {
p ^= q ^= p ^= q;
f = 1;
}
for (int i = 1; i <= p; ++i) while (check(i, f)) {
ans[++top] = i;
mode[top] = f;
}
for (int i = 1; i <= q; ++i) while (check(i, !f)) {
ans[++top] = i;
mode[top] = !f;
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (a[i][j]) {
cout << -1 << endl;
return 0;
}
}
}
cout << top << endl;
for (int i = 1; i <= top; ++i) {
if (!mode[i]) cout << "row ";
else cout << "col ";
cout << ans[i] << endl;
}
return 0;
}