Training Site
Sideways banner

Modern Art

Input: Standard Input (stdin)
Output: Standard Output (stdout)
Memory limit: 12 megabytes
Time limit: 1.0 seconds

You are a famous abstract artist. Your latest work involves throwing paint at a range of canvases. Given the dimensions of your canvas and position and spread of each paint throw, you would like to know how many square centimetres of the final work are of a particular colour.


Read the first line to obtain 3 space separated integers: the height H of the canvas in cm, the width W of the canvas in cm, and the number of paint throws N.

What follows are N lines (N \le 50), representing the paint throws in the order they were thrown in. Each line contains 3 integers and a single character, separated by spaces. The first two integers are the x and y coordinates (in cm) for the paint throw (0 \le x_i < W, 0 \le y_i < H). The third integer is the spread in cm (explained below). The final character indicates the colour of the paint being thrown.

The last line contains a single character, indicating a colour C.


Print a single integer, the number of square centimetres painted with the colour C in the final artwork. Note that more recently thrown colours might cover previous colours.


  • Subtask 1 (75%): Small canvases where 1 \le H, W \le 100
  • Subtask 2 (25%): Large canvases where 1 \le H, W \le 1{,}000{,}000


Paint always covers the square at the coordinates given. The spread indicates how many squares from the centre square the paint spreads. The overall coverage of a single throw is always a square shape. For example, a spread of 1 at coordinates (2, 1) would cover 9 square centimetres.

Sample Explained

In sample 1, you are given a canvas 5 cm high and 4 cm wide. A purple (p) colour is shown at coordinates (0, 0) with a spread of 0. A cyan (c) colour is also shown at coordinates (3, 2). The final square centimetre coverage of cyan (c) is therefore 6.

  • Sample Input 1

    5 4 2
    0 0 0 p
    3 2 1 c

    Sample Output 1