Fully Hidden Buildings

The city of Tetragon has a very regularly ordered layout. The city's roads form a square N x N grid of equally-sized blocks aligned to the four compass directions (North, West, South, East). On each block is built either a Large Building (such as an office building or highrise apartments), a Small Building (such as a school, library, or house), or it is left Empty (such as a park or parking lot).

When viewing the blocks along a compass direction (for example, from East to West), a Small Building would be hidden if it was positioned behind a Large Building or another Small Building. Likewise a Large Building would also be hidden behind another Large Building, but a Small Building is too small to hide a Large Building. A building is considered fully hidden if it is unable to be seen along any compass direction.

Small Buildings pictured in Blue, Large Buildings pictured in Red. Only the shaded buildings are considered fully hidden.

Problem Statement

Input Data
First line is N B, where N is the quantity of blocks along either edge of the city grid, and B is the total number of buildings to be found within the grid.
B lines will follow, each with three space-separated values type X Y, with type being either of the characters L or S to indicate a Large or Small building at the location, and the X Y values correspond to the building's position within the grid.

Answer
Should be Q space-separated integers, corresponding to total number of hidden buildings within the grid.

Example

input data:
4 11
L 0 1
S 0 2
S 1 0
L 1 2
L 1 3
L 2 0
S 2 1
L 2 2
L 2 3
S 3 1
L 3 2

answer:
2

Larger Example

input data:
100 1000
S 34 44
S 71 57
S 1 63
S 53 48
L 67 92
L 41 93
S 19 63
S 91 20
S 63 44
S 14 8
L 60 30
S 6 50
L 25 66
L 55 88
L 6 3
S 58 25
S 62 22
S 64 35
S 98 72
S 3 89
L 68 68
L 26 38
L 80 58
L 72 68
S 78 13
S 0 34
L 74 69
L 1 9
S 3 5
S 18 35
S 20 59
S 1 29
S 79 91
S 20 60
S 26 43
S 82 97
S 63 74
L 99 61
S 7 65
S 49 69
S 56 46
S 98 17
S 15 54
L 69 30
S 42 80
L 30 92
L 83 14
S 29 13
L 47 24
L 61 41
S 74 86
L 59 16
S 47 57
S 84 12
L 71 56
L 88 88
L 21 79
S 85 60
S 20 8
S 82 14
S 37 57
S 13 41
L 8 95
S 70 4
S 65 20
S 90 76
S 90 2
S 29 12
L 15 45
L 62 98
L 26 66
S 83 86
S 71 50
S 5 93
S 4 69
S 88 74
L 69 89
L 33 71
S 54 10
S 3 75
S 27 83
S 27 18
L 11 77
S 44 36
S 8 38
S 27 60
S 15 80
S 89 32
L 10 94
S 78 85
S 82 76
L 82 66
L 15 71
L 62 90
S 58 20
L 85 59
L 81 32
L 88 83
S 82 29
S 81 31
S 58 68
L 82 51
S 3 65
S 1 62
S 48 70
S 17 43
S 99 13
L 77 25
S 42 92
L 91 48
S 20 85
S 3 8
S 15 30
S 45 28
L 40 78
S 73 84
S 6 96
S 92 24
S 14 20
S 34 85
S 75 80
S 49 92
L 84 30
S 7 64
S 91 89
S 59 56
S 68 29
S 30 75
S 94 65
S 68 19
L 14 41
S 34 71
S 1 38
L 60 38
L 70 32
S 99 78
L 32 76
L 54 34
S 49 60
S 2 75
S 61 42
S 98 44
S 3 70
L 68 96
L 94 60
L 87 75
S 44 30
S 56 95
S 49 5
S 42 8
S 48 35
L 16 71
S 67 7
S 0 83
L 84 41
S 84 14
L 11 91
S 39 0
L 84 93
S 31 67
S 23 88
L 52 51
L 35 36
L 48 96
S 88 14
L 42 36
L 78 5
S 67 56
S 5 55
S 92 56
S 97 22
S 35 83
S 69 50
S 23 19
S 82 70
S 70 67
L 26 57
S 91 51
L 8 2
S 23 47
L 17 30
S 5 92
S 5 58
S 85 58
S 32 3
S 15 29
L 90 71
L 87 2
L 3 94
S 95 31
S 67 93
L 81 50
L 0 62
L 76 5
S 59 51
L 23 60
S 56 53
L 87 27
S 75 19
S 75 70
S 26 64
S 84 24
L 25 16
S 67 10
S 46 76
S 80 52
S 86 8
S 14 57
L 10 63
L 23 78
L 10 82
S 55 49
L 5 63
S 46 92
L 28 90
S 98 30
S 26 98
L 90 53
L 72 74
S 14 4
S 9 0
L 93 88
S 13 69
S 78 44
S 73 30
S 19 69
S 30 11
L 78 97
L 55 28
S 51 6
S 10 25
S 26 44
S 41 33
L 88 57
S 21 82
L 24 60
L 12 4
L 91 24
S 93 12
S 3 86
S 31 80
S 59 23
L 38 33
S 94 8
L 36 1
S 29 20
S 59 66
S 82 50
L 30 99
L 54 47
S 59 40
S 50 46
L 29 26
S 31 38
L 27 41
S 22 37
L 50 48
S 43 69
S 54 29
S 25 25
S 7 33
S 15 92
S 53 55
L 32 43
S 35 54
S 7 51
S 26 12
S 0 48
S 59 10
S 22 99
S 13 40
S 0 27
L 47 5
S 10 37
S 66 77
L 21 13
S 7 52
L 19 34
S 6 55
S 83 13
S 57 60
L 53 77
S 8 85
S 65 17
L 56 86
S 71 35
L 2 54
L 22 88
S 29 66
S 95 26
S 45 29
S 20 5
S 58 81
S 94 27
S 6 75
S 92 73
L 91 52
L 98 61
S 73 74
S 60 82
S 92 58
S 27 72
L 32 87
L 90 68
L 63 55
S 46 79
L 22 24
S 78 63
L 87 87
S 12 95
S 82 20
S 14 94
L 43 32
L 94 90
S 49 71
L 8 65
S 50 85
L 33 52
L 52 62
L 98 47
L 13 10
L 6 49
S 39 26
S 3 58
S 1 19
S 99 76
S 42 53
S 58 50
L 54 65
L 46 31
S 18 97
S 25 76
S 23 39
S 68 83
L 97 53
S 57 23
S 8 11
S 90 84
S 43 7
L 33 27
S 69 2
S 71 81
S 34 65
L 46 3
L 48 14
L 63 22
S 35 11
L 61 26
S 93 34
S 0 52
S 46 83
S 78 10
S 98 4
S 52 22
S 89 36
S 1 13
S 75 20
S 80 46
S 24 35
S 69 34
S 15 58
L 90 45
S 17 39
L 18 44
S 1 50
S 31 56
L 25 10
L 65 4
L 28 64
S 52 78
S 10 67
S 17 40
S 5 5
S 66 0
L 14 93
S 74 18
S 83 44
L 72 79
S 37 6
S 88 86
S 73 94
L 78 53
S 4 35
S 94 41
L 95 39
S 50 25
S 39 43
S 40 53
L 16 54
L 73 15
L 46 8
S 26 51
S 5 13
S 33 98
L 23 11
S 43 5
S 54 20
S 78 32
L 82 13
S 16 90
L 96 72
S 3 51
S 45 61
S 54 3
S 0 12
L 92 1
S 93 82
S 53 31
L 99 82
L 33 91
S 75 9
L 30 3
L 45 34
L 16 8
S 72 4
S 3 24
L 44 13
L 32 45
S 39 34
S 5 44
S 70 82
L 83 5
L 80 6
S 21 90
S 46 73
L 20 41
L 76 20
L 62 9
S 7 54
L 82 34
S 46 69
S 54 19
L 19 66
S 44 46
S 56 80
S 29 74
L 32 4
S 81 55
S 16 68
S 96 66
S 31 72
S 25 57
L 80 71
L 68 46
L 65 77
S 61 35
L 69 71
L 98 34
L 96 92
S 21 95
L 34 91
L 73 27
S 56 85
S 46 89
L 14 29
S 44 66
L 99 85
S 51 78
S 81 22
S 52 60
S 14 62
S 16 1
L 47 76
S 36 18
S 8 10
S 3 39
L 8 92
S 84 25
L 99 83
S 46 27
S 76 48
L 42 61
S 9 79
S 48 1
L 81 58
S 52 76
S 79 54
S 33 46
L 57 1
S 32 95
L 93 19
S 96 56
L 32 85
L 72 45
L 32 56
S 87 86
S 33 22
L 63 27
L 73 17
S 25 23
L 26 87
L 71 28
L 47 62
S 99 9
S 59 53
S 18 80
L 18 37
S 62 5
L 50 30
S 60 98
S 12 35
S 95 71
S 57 36
S 46 6
S 30 0
S 25 24
L 69 83
S 3 60
S 6 17
L 15 97
S 60 4
S 55 10
S 6 4
L 54 73
L 24 64
S 49 36
S 4 71
L 91 23
S 78 27
S 6 36
S 35 69
L 62 93
S 76 52
L 32 8
L 69 61
L 39 46
S 96 43
S 66 60
S 25 99
S 15 52
S 69 78
L 87 8
L 18 83
L 48 61
L 13 4
S 72 15
S 85 54
S 54 7
S 46 43
S 76 25
S 81 97
S 6 70
L 21 51
S 21 10
S 70 73
S 16 64
S 53 35
L 48 64
S 35 51
S 32 67
S 97 46
S 89 46
S 51 89
S 85 27
S 33 64
S 50 83
S 60 22
S 14 66
S 49 8
S 31 51
S 99 48
S 84 29
S 5 35
S 24 81
S 65 67
L 17 32
S 31 57
S 63 56
L 90 30
L 89 30
L 29 65
S 27 47
S 1 7
S 58 64
S 75 62
S 55 83
L 45 40
S 3 29
L 64 3
S 30 83
S 86 77
S 50 31
S 64 76
S 67 98
L 79 46
L 27 84
S 42 14
S 1 46
L 39 20
S 58 51
S 39 81
S 94 96
L 32 68
S 84 98
S 21 17
S 48 60
S 24 72
L 96 89
S 36 17
S 83 40
S 55 55
L 97 78
S 97 97
S 3 7
S 99 38
L 93 30
S 87 56
S 12 53
S 75 15
S 93 53
S 34 80
L 39 80
S 18 79
S 82 22
S 43 36
S 17 50
S 67 2
S 64 21
S 81 61
S 47 49
L 54 32
L 24 1
S 37 66
L 13 26
S 39 72
S 87 69
S 85 43
L 4 65
S 55 32
L 78 95
S 16 17
S 75 18
S 35 86
S 46 50
S 74 63
L 72 81
S 25 50
S 30 45
S 52 53
S 19 30
L 6 90
L 93 84
S 34 41
S 75 53
L 15 64
S 82 44
L 17 12
S 61 94
L 20 99
L 66 11
S 87 6
S 90 28
S 13 44
L 26 75
L 96 98
L 41 69
S 2 55
L 38 64
S 43 21
L 95 99
L 41 6
S 71 65
S 34 67
S 52 25
S 78 9
L 95 21
L 72 36
S 76 23
S 89 62
S 70 81
S 56 97
S 90 56
S 30 88
S 15 94
S 73 31
S 27 38
S 53 86
S 55 34
S 58 93
S 43 59
S 74 35
S 30 62
S 24 54
S 3 42
S 25 40
L 22 39
S 37 25
S 89 84
S 24 58
L 51 9
L 16 13
L 44 88
S 56 59
S 65 81
S 73 90
S 41 66
L 93 73
L 76 67
S 58 22
S 25 45
S 73 35
S 98 10
S 67 59
L 74 47
L 51 72
S 28 63
S 83 76
L 87 54
L 20 68
S 11 13
S 39 14
L 50 68
S 58 54
L 83 52
S 79 20
S 0 70
S 17 15
L 80 28
L 59 35
S 71 21
L 31 29
L 65 30
S 95 29
S 77 7
S 68 33
L 70 57
S 49 56
S 49 66
L 66 76
L 42 50
S 48 93
L 14 92
S 42 74
S 52 71
L 95 35
S 17 36
S 52 23
L 56 8
S 96 48
S 98 90
L 95 38
S 46 0
L 71 48
S 47 77
S 79 93
S 55 87
S 79 25
S 83 89
L 79 8
S 13 42
S 14 97
S 74 46
L 72 18
S 49 17
S 40 50
S 61 54
S 70 75
S 31 10
S 92 43
S 1 99
S 2 84
S 21 59
S 90 78
S 71 8
S 78 58
S 82 71
L 56 27
S 43 99
L 36 13
L 33 45
L 75 23
S 91 26
L 28 73
L 18 54
S 23 21
S 39 31
L 16 38
S 72 87
L 28 72
S 17 99
S 62 0
S 2 59
S 81 48
S 35 71
S 41 28
S 42 70
L 80 76
S 48 42
L 27 34
L 50 59
S 21 38
S 22 86
S 37 55
S 76 14
S 77 14
S 97 15
S 72 35
S 55 6
S 50 74
S 50 54
S 14 3
S 43 63
S 78 42
S 26 13
L 38 26
L 21 50
S 0 87
S 16 85
S 98 9
S 0 73
S 19 32
L 34 10
S 80 99
S 58 43
S 59 64
S 50 34
S 56 33
L 25 42
S 76 85
S 67 12
L 81 67
S 13 53
S 34 60
L 92 40
S 4 57
L 87 18
S 21 26
S 64 6
S 59 70
S 79 63
S 76 45
L 0 72
S 53 2
S 13 88
S 26 73
L 32 10
L 57 83
L 83 10
S 27 85
S 85 69
S 97 74
L 74 84
S 24 97
S 83 28
S 1 33
S 40 92
S 17 96
S 41 17
L 73 8
L 53 66
L 0 97
S 44 94
S 89 18
L 43 58
S 96 49
S 12 0
S 49 28
S 63 17
S 55 56
L 30 95
S 73 66
L 84 59
S 10 52
S 83 4
S 80 96
S 76 77
S 10 91
L 23 92
S 88 70
S 51 21
L 56 13
L 20 61
S 65 16
S 71 53
L 22 28
L 69 23
L 63 5
S 33 84
L 67 65
S 7 27
L 81 96
S 22 84
S 12 77
L 4 98
L 54 14
S 82 88
L 22 9
L 50 92
S 16 2
S 16 50
S 23 95
S 45 1
S 27 88
L 81 88
L 53 84
S 1 44
S 11 86
S 67 99
S 27 54
L 83 19
S 68 25
S 75 55
S 67 90
S 46 18
S 70 55
S 7 79
S 60 73
S 30 85
S 84 74
S 18 50
S 17 22
L 10 31
L 19 80
S 90 81
L 47 9
S 5 56
L 13 98
S 43 26
L 85 41
S 66 72
S 39 79
L 32 6
S 55 22
S 2 85
S 86 73
L 18 43
S 57 38
S 99 45
L 1 3
L 32 33
S 31 8
L 12 9
L 87 40
S 23 64
S 34 56
L 23 34
L 99 17
S 28 40
S 66 12
L 81 16
L 89 53
S 73 61
L 60 78
L 52 81
S 44 56
S 66 37
L 80 62
S 40 76
L 77 52
L 96 55
L 42 24
S 7 98
S 54 71
S 60 75
L 23 29
S 84 71
L 30 5
S 53 59
S 34 53
L 59 69
S 34 84
L 85 57
S 74 80
L 24 5
S 53 50
L 43 35
S 90 55
S 33 92
S 19 12
S 88 87
L 28 82
S 84 27
S 25 67
S 34 38
S 80 13
S 85 85
S 31 21
L 24 13
S 84 62
S 21 0
S 55 13
L 62 30
L 91 95
S 30 47
S 74 44
S 50 20
L 68 60
S 97 51
L 17 16
S 77 48
S 73 58
S 60 28
S 78 16
L 66 52
S 12 90
S 50 13
S 19 79
S 60 83
S 38 94
L 63 52

answer:
487 
(421 Small hidden, 66 Large hidden)