My brute force solution with complexity O(n*n*p*q) ~ 10^12  have got AC. So add test generated by this programm and some similar, please.

#include <stdio.h>

int i, n, p;

int main() {
    n = 5000;
    printf("%d 2\n", n);
    printf("3 3 2 2 3\n");
    printf("4970 4970 2 2 3\n");
    p = 345;
    printf("%d\n", p);
    for (i = 0; i < p; i ++) {
        printf("%d %d %d %d %d %d %d %d %d\n", i+1, n - 2 - i, 1, n - 2, 1, -1, 0, 0, p);
    }
    return 0;
}

Hm-hm-hm... IMHO, quite obvious anti-BF test. Despondently that problemsetter didn't add it - many inefficient solutions may got AC even during real contest!

Thank you for test. We've added it and rejudged the problem. And you are the only author who don't pass this test. :) Maybe some new tests will be added later. If you have other good tests, please, send them to timus_support (at) acm.timus.ru