#P18598. Flower Garden

Flower Garden

Flower Garden

题目描述

Bytingham 宫殿前有一座美丽的花园,每年都有许多游客慕名前来。国王 Intles III 多年来主要致力于把花园修得更长,如今已经能沿一条直线种下 3n3n 朵花。

之前的园丁花费了大量心血,却在不到四十岁时便决定提前退休。你来到宫殿接任工作。前任的面容让你怀疑自己对年龄的判断,但你还是欣然接受了职位,现在迎来了第一个任务。

今年花园里只种两种花:紫罗兰和玫瑰。国王的法令规定了种植方案。花圃位置依次编号为 1,2,…,3n1,2,\ldots,3n,每个位置恰好种一朵花。

法令共有 qq 条要求。第 ii 条给出四个整数 ai,bi,ci,dia_i,b_i,c_i,d_i,要求下列两件事至少有一件成立:

  • 从 aia_i 到 bib_i 的所有位置都种玫瑰;
  • 从 cic_i 到 did_i 的所有位置都种紫罗兰。

更令人头痛的是,法令最后一页写道:只有 2n2n 朵玫瑰和 2n2n 朵紫罗兰可供使用。因此,种下的每种花的数量都不能超过 2n2n。

请给出满足全部法令和花朵数量限制的种植方案,或判断无解。

输入格式

第一行一个整数 zz,表示测试用例数,1≤z≤1000001\le z\le100000。

每个测试用例:

  • 第一行两个整数 n,qn,q,满足 1≤n≤333331\le n\le33333、1≤q≤1000001\le q\le100000。
  • 接下来 qq 行,第 ii 行四个整数 ai,bi,ci,dia_i,b_i,c_i,d_i,描述第 ii 条法令,满足1≤ai≤bi≤3n,1≤ci≤di≤3n.1\le a_i\le b_i\le3n,\qquad1\le c_i\le d_i\le3n.

所有测试用例的 nn 之和不超过 333333333333,qq 之和不超过 10000001000000。

输出格式

对每个测试用例:

  • 若无解,输出一行 NIE。
  • 否则输出一行 TAK,再输出一行长度为 3n3n 的字符串,只能包含 F 和 R。第 ii 个字符 F 表示第 ii 个位置种紫罗兰,R 表示种玫瑰。

字符串中 F 的数量和 R 的数量都不能超过 2n2n。有多种正确方案时,输出任意一种。

样例输入 1

2
1 3
1 1 2 2
1 2 3 3
1 1 3 3
1 3
1 1 2 2
2 2 3 3
3 3 1 1

样例输出 1

TAK
RFF
NIE