1. Better Compression

Consider a string S that is a series of characters, each followed by its frequency as an integer. The string is not compressed correctly, so there may be multiple occurrences of the same character. A properly compressed string will consist of one instance of each character in alphabetical order followed by the total count of that character within the string.

Example

The string "a3c9b2c1" has two instances where 'c' is followed by a count: once with 9 occurrences, and again with 1 occurrence. It should be compressed to "a3b2c10".

Function Description

Complete the function betterCompression in the editor below.

betterCompression has the following parameter:

• S: a compressed string.

Returns:

• string: the properly compressed string.

Constraints

• 1 ≤ size of S ≤ 100,000
• 'a' ≤ characters in S ≤ 'z'
• 1 ≤ frequency of each character in S ≤ 1000

---

Input Format for Custom Testing

The first line contains a string S.

---

Sample Case 0

Input:

STDIN Function
a12b56c1 → S = 'a12b56c1'

Output:

a12b56c1

Explanation: Nothing is changed because each character occurred only once, and they are already sorted in ascending order.

---

Sample Case 1

Input:

STDIN Function
a12c56a1b5 → S = 'a12c56a1b5'

Output:

a13b5c56

Explanation: 'a' occurs twice: 12 times in the first occurrence and 1 time in the second occurrence, for a total of 13. The characters 'b' and 'c' are sorted in alphabetical order in the final result.

---

2. Do They Belong?

Given three points a(x1, y1), b(x2, y2), and c(x3, y3), check if they form a non-degenerate triangle. Then, verify if two points, p(xp, yp) and q(xq, yq), are inside or on the triangle. Return the appropriate scenario number.

Scenarios

1. 0: The lines do not form a valid non-degenerate triangle.
2. 1: Point p belongs to the triangle, but point q does not.
3. 2: Point q belongs to the triangle, but point p does not.
4. 3: Both points p and q belong to the triangle.
5. 4: Neither point p nor q belong to the triangle.

---

Note

A triangle is considered non-degenerate if it meets the following conditions (where |ab| denotes the length of the line segment between points a and b):

• |ab| + |bc| > |ac|
• |bc| + |ac| > |ab|
• |ab| + |ac| > |bc|

---

Example

Given:

• a(x1, y1): (2, 2)
• b(x2, y2): (7, 2)
• c(x3, y3): (5, 4)
• p(xp, yp): (4, 3)
• q(xq, yq): (7, 4)

First, the triangle abc forms a valid non-degenerate triangle.
Second, point p(4, 3) belongs to the triangle, but point q(7, 4) does not.

Answer: 1

---

Function Description

Complete the function pointsBelong in the editor below.

---

Function Parameters

• int x1, y1, x2, y2, x3, y3: Integer coordinates of the three points that may create a valid triangle.
• int xp, yp, xq, yq: Integer coordinates of the two points p and q.

Returns:

• int: The scenario number.

Constraints

• 0 ≤ x1, y1, x2, y2, x3, y3, xp, yp, xq, yq ≤ 2000

---

Input Format for Custom Testing

Sample Input 0:

STDIN Function
0 → (x1, y1) = (0, 0)
0 → (x2, y2) = (2, 0)
4 → (x3, y3) = (4, 0)
0 → (xp, yp) = (2, 0)
0 → (xq, yq) = (4, 0)

Sample Output 0:

0

Explanation: The lines do not form a valid non-degenerate triangle: The three points a, b, and c lie on the same line, so it is impossible to form a triangle. The answer is 0.

---

我们长期稳定承接各大科技公司如TikTok、Google、Amazon等的OA笔试代写服务，确保满分通过。如有需求，请随时联系我们。

We consistently provide professional online assessment services for major tech companies like TikTok, Google, and Amazon, guaranteeing perfect scores. Feel free to contact us if you're interested.